The Fellow Programmer

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to] , reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK . Thus, the itinerary must begin with JFK . Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"] . All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. One must use all the tickets once and only once. Example 1: Input: [["MUC", "LHR&quo

Given a positive integer n , find the least number of perfect square numbers (for example, 1, 4, 9, 16, ... ) which sum to n . Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.   class Solution {     public int numSquares(int n) {    int[] dp = new int[n + 1];     int near, min;     for (int i = 1; i <= n; i++) {         near = (int) Math.sqrt(i);          min = dp[i - 1];         for (int j = near; j > 0; j--) {                 min = Math.min(dp[i - j * j], min);         }         dp[i] = min + 1;     }     return dp[n]; } } Try it on Leetcode Here, we are going to solve problem using bottom up DP(Dynamic Programming). 1) Initialize dp array having size of n+1. 2) i variable iterates from 1 to n and for each i values we find nearest square number (near variable). 3) j iterates from near to 1 and for each j value we find Math.min(dp[i - j * j], min) . After finding min

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123 . Find the total sum of all root-to-leaf numbers. Note:  A leaf is a node with no children. Example: Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12 . The root-to-leaf path 1->3 represents the number 13 . Therefore, sum = 12 + 13 = 25 . Example 2: Input: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026 .   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     Tr

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Note: You must not modify the array (assume the array is read only). You must use only constant, O (1) extra space. Your runtime complexity should be less than O ( n 2 ). There is only one duplicate number in the array, but it could be repeated more than once. METHOD 1:   class Solution {     public int findDuplicate(int[] nums) {         ArrayList<Integer>list = new ArrayList<Integer>();                 for(int num:nums){             if(list.contains(num)){                 return num;             }             else{                 list.add(num);             }         }         return -1;     } } Try it on Leetcode Here, we are doing with

Given a string s and a non-empty string p , find all the start indices of p 's anagrams in s . Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter. Example 1: Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc". Example 2: Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab". METHOD 1:   class Solution { public List<Intege

Given n , how many structurally unique BST's (binary search trees) that store values 1 ...  n ? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3   class Solution {     public int numTrees(int n) {          int countUniqueTrees[] = new int[n + 1];         countUniqueTrees[0] = 1;     countUniqueTrees[1] = 1;       for (int i = 2; i <= n; i++)      {         for (int j = 1; j <= i; j++)          {             countUniqueTrees[i] = countUniqueTrees[i] + (countUniqueTrees[i - j] *                               countUniqueTrees[j - 1]);         }     }       return countUniqueTrees[n];     } } Try it on Leetcode The idea behind solving this problem is , for all possible values of i, consider i as root, such that 1....i-1 will com