Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Naive Way: In order to find a minimum window, there must be a way to represent the pattern (which is T) here and current accumulate characters set. A map is suitable to deal with that. Map each character to # of its appearance. And then, need to find a way to keep track of every possible position when a match was found and you need to delete the first character from current accumulate char set. A queue is suitable to do that.

A case when S = "bba" and T="ab" leads to  this line.

  while(isMatch(pattern, cur)){ /* Important Code! */  

One shortcoming is isMatch() funciton takes O(T) time.

 public class Solution {  
   public String minWindow(String S, String T) {  
     Map<Character, Integer> pattern = new HashMap<Character, Integer>();  
     Map<Character, Integer> cur = new HashMap<Character, Integer>();  
     Queue<Integer> queue = new LinkedList<Integer>();  
     int min = Integer.MAX_VALUE;  
     int begin = 0, end = 0;  
     // fill in pattern by T  
     for(int i = 0;i < T.length();i++) addToMap(pattern, T.charAt(i));  
     // initialize current set  
     for(int i = 0;i < T.length();i++) cur.put(T.charAt(i), 0);  
     // go through S to match the pattern by minimum length  
     for(int i = 0;i < S.length();i++){  
       if(pattern.containsKey(S.charAt(i))){  
         queue.add(i);  
         addToMap(cur, S.charAt(i));  
         // check if pattern is matched  
         while(isMatch(pattern, cur)){ /* Important Code! */  
           if(i - queue.peek() < min){  
             min = i - queue.peek();  
             begin = queue.peek();  
             end = i+1;  
           }  
           cur.put(S.charAt(queue.peek()), cur.get(S.charAt(queue.peek()))-1);  
           queue.poll();  
         }  
       }  
     }  
     return end > begin?S.substring(begin, end):"";  
   }  
   private void addToMap(Map<Character, Integer> map, Character c){  
     if(map.containsKey(c))  
       map.put(c, map.get(c)+1);  
     else  
       map.put(c,1);  
   }  
   private boolean isMatch(Map<Character, Integer> p, Map<Character, Integer> cur){  
     for(Map.Entry<Character, Integer> entry: p.entrySet())  
       if(cur.get((char)entry.getKey()) < (int)entry.getValue()) return false;  
     return true;  
   }  
 }  

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Naive Way: There lies a linear approach O(n+m).

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     // edge case  
     if(matrix==null || matrix.length==0) return false;  
     // general case  
     int i = 0, j = matrix[0].length-1;  
     while(i < matrix.length && j >= 0){  
       if(matrix[i][j] == target) return true;  
       if(matrix[i][j] > target) j--;  
       else i++;  
     }  
     return false;  
   }  
 }  

The idea is to start from upper right. If current number is larger than target, that means you cannot find target in current row. So turn to next row. If current number is smaller than target, that means the target must lie in current row.

Improved Way: Could use a binary search approach to search current row/column. Speed up the approach to O(logn + logm) = O(log(nm))

 public class Solution {  
   public boolean searchMatrix(int[][] matrix, int target) {  
     // edge case  
     if(matrix==null || matrix.length==0) return false;  
     // general case  
     int row = binarySearch(matrix, target);  
     if(row==-1) return false;  
     int col = binarySearch(matrix[row], target);  
     return col!=-1;  
   }  
   private int binarySearch(int[][] matrix, int target){  
     int low = 0, high = matrix.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(matrix[middle][0] <= target && middle==matrix.length-1) return middle;  
       if(matrix[middle][0] <= target && matrix[middle+1][0] > target) return middle;  
       if(matrix[middle][0] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return low;  
   }  
   private int binarySearch(int[] array, int target){  
     int low = 0, high = array.length-1;  
     while(low <= high){  
       int middle = (low+high)/2;  
       if(array[middle] == target) return middle;  
       if(array[middle] > target) high = middle-1;  
       else low = middle+1;  
     }  
     return -1;  
   }  
 }  

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Naive Way: A DP approach should be able to conquer this problem. The basic logic is

opt[i] // # of distinct ways to reach top
// base case
opt[0] = 1, opt[1] = 1 (edge case should be n=0, return 0)
// iteration
opt[i] = opt[i-1]+opt[i-2]

 public class Solution {  
   public int climbStairs(int n) {  
     // DP  
     // edge case  
     if(n == 0) return 0;  
     int opt[] = new int[n+1];  
     // base case  
     opt[0] = 1;  
     opt[1] = 1;  
     // iteration  
     for(int i = 2;i <= n;i++) opt[i] = opt[i-1]+opt[i-2];  
     return opt[n];  
   }  
 }  

It turns out this follows Fibonacci Sequence. So there is a famous DFS recursive method. Could use path memorizing to reduce time complexity from O(2^n) to O(n).

 public class Solution {  
   public int climbStairs(int n) {  
     // DFS  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     map.put(0,1);  
     map.put(1,1);  
     return dfs(n, map);  
   }  
   private int dfs(int n, Map<Integer, Integer> map){  
     // fast ending  
     if(map.containsKey(n)) return map.get(n);  
     // recursion  
     int rslt = dfs(n-1, map) + dfs(n-2, map);  
     map.put(n, rslt);  
     return rslt;  
   }  
 }  

Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.

Naive Way: Return the square root of an integer as an integer. I use binary search. First I need to find maximum possible square root, which is (int)Math.sqrt(Integer.MAX_VALUE). And when it happens sqrt(x) is this value, can't use i^2 <= x <(i+1)^2 to end the loop since (i+1)^2 will overflow. List this case separately.

 public class Solution {  
   static final int MAX_SQRT = (int)Math.sqrt(Integer.MAX_VALUE);  
   public int sqrt(int x) {  
     int high = MAX_SQRT, low = 0;  
     while(low <= high){  
       int middle = (high+low)/2;  
       if(middle*middle <= x && middle == MAX_SQRT) return middle;  
       if(middle*middle <= x && (middle+1)*(middle+1) > x) return middle;  
       if(middle*middle > x)  
         high = middle-1;  
       else  
         low = middle+1;  
     }  
     return low;  
   }  
 }  

Improved Way: There is a mathematical method Newton's Method. I can't understand what is stated in the link. There are too mathematical. I understand from other one's algorithm newtons-iterative-method-in-c . In the answer of that question. Newton's method was explained.

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.
For example,
Given n = 3,
You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
] 

Naive Way: Use what I write in Spiral Matrix. Key point is current row/column 's fill in length get minus by one every two steps.
I comment what each parameter represents. Easy to understand and good looking.

 public class Solution {  
   public int[][] generateMatrix(int n) {  
     int[][] m = new int[n][n];  
     int len = n; // current row/column 's fill in length  
     int index = 0; // direction controller  
     int number = 1; // increasing numbers  
     int x = 0, y = -1; // current position  
     // fill in the matrix  
     while(len > 0){  
       if(index%2==1) len--;  
       switch(index++%4){  
         case 0:  
           for(int i = 0;i < len;i++) m[x][++y] = number++;  
           break;  
         case 1:  
           for(int i = 0;i < len;i++) m[++x][y] = number++;  
           break;  
         case 2:  
           for(int i = 0;i < len;i++) m[x][--y] = number++;  
           break;  
         case 3:  
           for(int i = 0;i < len;i++) m[--x][y] = number++;  
           break;  
         default:  
         break;  
       }  
     }  
     return m;  
   }  
 }  

Length of Last Word Total

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.

Naive Way: This question is relatively easy. The edge case is the testing point. All the edge case I can came up with are,

• ""
• " "
• "   "
• "word  "
• "word"

So, basically keep two pointers and eliminate all tailing white-spaces.

 public class Solution {  
   public int lengthOfLastWord(String s) {  
     int i = s.length()-1;  
     int len = 0;  
     while(i >= 0 && s.charAt(i) == ' ') i--;  
     while(i >= 0 && s.charAt(i) != ' '){len++;i--;}  
     return len;  
   }  
 }  

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].


Naive Way: This question contains no fancy algorithm as far as I know. Just find where the new interval should be merged into. I try to implement it naively in one pass. But there are so many edge cases I never thought about. I list some of them.

• Empty set of intervals [].
• New interval doesn't have overlap with any of the intervals in the set.
• New interval is before first interval of the set.
• New interval is after last interval of the set.

After including all these edge cases. My code is a little tedious. Use a new List to hold result, which requires O(n) space.

 /**  
  * Definition for an interval.  
  * public class Interval {  
  *   int start;  
  *   int end;  
  *   Interval() { start = 0; end = 0; }  
  *   Interval(int s, int e) { start = s; end = e; }  
  * }  
  */  
 public class Solution {  
   public List<Interval> insert(List<Interval> intervals, Interval newInterval) {  
     List<Interval> rslt = new ArrayList<Interval>();  
     // edge case  
     if(intervals.size()==0) rslt.add(newInterval);  
     // merge intervals  
     int begin = -1, end = -1;  
     for(int i = 0;i < intervals.size();i++){  
       // if no overlapping with newInterval at all  
       if(intervals.get(i).start > newInterval.end && i==0)  
         rslt.add(newInterval);  
       // if current interval overlap with newInterval, merge them  
       if(overlap(intervals.get(i), newInterval)){  
         if(begin==-1) begin = Math.min(intervals.get(i).start, newInterval.start);  
         end = Math.max(intervals.get(i).end, newInterval.end);  
         // when last interval overlaps  
         if(i==intervals.size()-1){  
           Interval mergedInterval = new Interval(begin, end);  
           rslt.add(mergedInterval);  
         }  
       }else{  
         if(begin!=-1){  
           // if overlap ends, add newly merged interval  
           Interval mergedInterval = new Interval(begin, end);  
           rslt.add(mergedInterval);  
           begin = -1;  
         }  
         rslt.add(intervals.get(i));  
       }  
       // if no overlapping with newInterval at all  
       if(intervals.get(i).end < newInterval.start && (i!=intervals.size()-1 && intervals.get(i+1).start > newInterval.end || i==intervals.size()-1))  
         rslt.add(newInterval);  
     }  
     return rslt;  
   }  
   private boolean overlap(Interval a, Interval b){  
     if(a.start <= b.start)  
       return a.end >= b.start;  
     else  
       return b.end >= a.start;  
   }  
 }  

Improved Way: There are much better and concise Solutions in Discuss Board. I steal one from inplace-and-concise-lines-java-solution-for-your-reference.
Its idea is to find the correct position for new interval, merge if necessary.

 public class Solution {  
   public List<Interval> insert(List<Interval> intervals, Interval newInterval) {  
     Iterator<Interval> iter = intervals.iterator();  
     int index = 0;  
     while(iter.hasNext()){  
       Interval cur = iter.next();  
       if(cur.end < newInterval.start){ index++; continue;}  
       if(cur.start > newInterval.end) break;  
       newInterval.start = Math.min(newInterval.start, cur.start);  
       newInterval.end = Math.max(newInterval.end, cur.end);  
       iter.remove();  
     }  
     intervals.add(index, newInterval);  
     return intervals;  
   }  
 }  

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

Naive Way: I first think about Greedy. Go as far as possible each jump. But a future longer jump may lie in previous step. So I just think greedy is not able to handle this problem. Then I turn to DP. It seems DP will handle this problem easily.The basic logic is

opt[i] // whether a position can be reached or not
// base case
opt[0] = true;
// iteration
opt[i] = (opt[t] && A[t]+t >= i) for all 0<=t < i

But this approach get Time Limited Error.

An O(n^2) DP will get TLE, which implies an O(n) solution exists.

Then I think about DFS with path memorizing. Start from the end, trace backward to see if a particular position can reach the final stage. I am having trouble correctly writing the algorithm so far.


An ideal approach is a greedy one. Keep a range [start, end] that you are going to traversal. Update the range [end, new_end] according to farest distance one can go on [start, end].

 public class Solution {  
   public boolean canJump(int[] A) {  
     // Greedy  
     if(A == null || A.length==0) return true;  
     int start = 0, end = A[0];  
     while(start <= end){  
       if(end >= A.length-1) return true;  
       int pre_end = end;  
       for(int i = start;i <= pre_end;i++)  
         end = Math.max(end, i+A[i]);  
       start = pre_end+1;  
     }  
     return false;  
   }  
 }  

Improved Way: A much more simple greedy idea. Update current coverage each step.

 public class Solution {  
   public boolean canJump(int[] A) {  
     // Greedy  
     int coverage = 0;  
     for(int i = 0;i < A.length;i++)  
       if(coverage < i)   
         return false;  
       else  
         coverage = Math.max(coverage, A[i]+i);  
     return true;  
   }  
 }  

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Naive Way: In order to traversal the matrix in spiral order, I need to keep two lengths, one is the current length of row that need to be traversal, one is the current length of column that need to be traversal. Also use a variable to control direction. Like 0-> going left, 1-> going down, 2-> going right, 3-> going up.

 public class Solution {  
   public List<Integer> spiralOrder(int[][] matrix) {  
     List<Integer> rslt = new ArrayList<Integer>();  
     if(matrix.length==0) return rslt;  
     int rowLen = matrix[0].length, colLen = matrix.length-1;  
     int x = 0, y = -1;  
     int dir = 0;  
     while(rowLen >= 0 && colLen >= 0){  
       switch(dir){  
         case 0:  
           for(int i = 0;i < rowLen;i++) rslt.add(matrix[x][++y]);  
           rowLen--;  
           break;  
         case 1:  
           for(int i = 0;i < colLen;i++) rslt.add(matrix[++x][y]);  
           colLen--;  
           break;  
         case 2:  
           for(int i = 0;i < rowLen;i++) rslt.add(matrix[x][--y]);  
           rowLen--;  
           break;  
         case 3:  
           for(int i = 0;i < colLen;i++) rslt.add(matrix[--x][y]);  
           colLen--;  
           break;  
       }  
       dir = ++dir%4;  
     }  
     return rslt;  
   }  
 }  

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

Naive Way: The algorithm for this problem should be simple, which is direct multiplication. However, multiply string will have a lot of corner cases. List all corner cases that I can think of.

• -/+ at the front
• "." fraction number in the middle
• extra zeros at tail

And then, when I was running the program, I found extra corner cases such as,

• result "00" should be "0"
• result "0.0" should be "0"

I write two sub functions. One if multiply a string by an integer. The other is plus two String. Because to multiply two strings, I need to multiply a String by one digit each time, and then sum up the results. I also keep a map to record calculated products to speed up the process.

 public class Solution {  
   public String multiply(String num1, String num2) {  
     String rslt = "0";  
     Map<Integer, String> map = new HashMap<Integer, String>();  
     // Eliminate "." for num1 and num2, put them into new String. Get "." position. Get -/+  
     int pointPosition = 0;  
     boolean negative = false;  
     StringBuilder n1 = new StringBuilder();  
     StringBuilder n2 = new StringBuilder();  
     for(int i = 0;i < num1.length();i++)   
       if(num1.charAt(i)=='.') pointPosition+= num1.length()-1-i;  
       else if(num1.charAt(i) =='-') negative = !negative;  
       else if(num1.charAt(i)!='+') n1.append(num1.charAt(i));  
     for(int j = 0;j < num2.length();j++)  
       if(num2.charAt(j)=='.') pointPosition+= num2.length()-1-j;  
       else if(num2.charAt(j) =='-') negative = !negative;  
       else if(num2.charAt(j)!='+') n2.append(num2.charAt(j));  
     // multiply one digit each time  
     for(int j = n2.length()-1;j >= 0;j--){  
       int digit = (int)(n2.charAt(j)-'0');  
       if(digit!=0){  
         String product;  
         if(map.containsKey(digit))  
           product = map.get(digit);  
         else  
           product = multiply(n1.toString(), digit);  
         map.put(digit, product);  
         if(!product.equals("0"))  
           for(int u = 0;u < n2.length()-1-j;u++) product += "0";  
         rslt = plus(rslt, product);  
       }  
     }  
     // add "."  
     if(pointPosition > rslt.length()-1)  
       for(int u = 0;u < pointPosition - (rslt.length()-1);u++)  
         rslt = "0" + rslt;  
     if(pointPosition!=0)  
       rslt = rslt.substring(0, rslt.length()-pointPosition) + "." + rslt.substring(rslt.length()-pointPosition, rslt.length());  
     // get rid of tail zeros when it's fraction number   
     if(pointPosition!=0)  
       while(rslt.length() > 1 && (rslt.charAt(rslt.length()-1) == '0' || rslt.charAt(rslt.length()-1) == '.'))  
         rslt = rslt.substring(0, rslt.length()-1);  
     // add sign  
     if(negative) rslt = "-"+rslt;  
     return rslt;  
   }  
   public String multiply(String num1, int num2){  
     int i = num1.length();  
     int carry = 0;  
     StringBuilder str = new StringBuilder();  
     while(--i >= 0){  
       int product = (int)(num1.charAt(i)-'0') * num2 + carry;  
       int remain = product%10;  
       carry = product/10;  
       str.append((char)('0'+remain));  
     }  
     if(carry!=0) str.append((char)('0'+carry));  
     return str.reverse().toString();  
   }  
   public String plus(String num1, String num2) {  
     int carry = 0;  
     StringBuilder rslt = new StringBuilder();  
     int i = num1.length()-1, j = num2.length()-1;  
     while(i >= 0 && j >= 0){  
       int value = (int)(num1.charAt(i)-'0') + (int)(num2.charAt(j)-'0') + carry;  
       carry = value/10;  
       value = value%10;  
       rslt.append((char)(value+'0'));  
       i--;  
       j--;  
     }  
     while(i >= 0){  
       int value = (int)(num1.charAt(i)-'0') + carry;  
       carry = value/10;  
       value = value%10;  
       rslt.append((char)(value+'0'));  
       i--;  
     }  
     while(j >= 0){  
       int value = (int)(num2.charAt(j)-'0') + carry;  
       carry = value/10;  
       value = value%10;  
       rslt.append((char)(value+'0'));  
       j--;  
     }  
     if(carry!=0) rslt.append((char)(carry+'0'));  
     return rslt.reverse().toString();  
   }  
 }  

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

Naive Way: Constant space here is a big constrain. The key here is by swapping. Since the length of the array is fixed. There can be at most array.length positive integers. Find the correct position for each valid positive integer by swapping. That will achieve constant space.

 public class Solution {  
   public int firstMissingPositive(int[] A) {  
     int i = 0;  
     while(i < A.length){  
       if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;  
       else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);  
       else i++;  
     }  
     i = 0;  
     while(i < A.length && A[i] == i+1) i++;  
     return i+1;  
   }  
   private void swap(int[] A, int i, int j){  
     int temp = A[i];  
     A[i] = A[j];  
     A[j] = temp;  
   }  
 }  

Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Naive Way: It's the same with  combination-sum . Just change the iteration index to index+1.

DFS iterative method

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Stack<SumNode> stack = new Stack<SumNode>();  
     Arrays.sort(num);  
     SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());  
     stack.push(root);  
     while(!stack.isEmpty()){  
       SumNode node = stack.pop();  
       for(int i = node.index+1;i < num.length;i++){  
         if(node.sum + num[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(num[i]);  
         if(child.sum==target) set.add(child.path);  
         else stack.push(child);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

BFS iterative method

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Queue<SumNode> queue = new LinkedList<SumNode>();  
     Arrays.sort(num);  
     SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());  
     queue.add(root);  
     while(!queue.isEmpty()){  
       SumNode node = queue.poll();  
       for(int i = node.index+1;i < num.length;i++){  
         if(node.sum + num[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(num[i]);  
         if(child.sum==target) set.add(child.path);  
         else queue.add(child);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

Recursive Method:

 public class Solution {  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Arrays.sort(num);   
     dfs(num, -1, target, 0, new ArrayList<Integer>(), set);  
     rslt.addAll(set);  
     return rslt;   
   }  
   private void dfs(int[] n, int index, int target, int sum, List<Integer> path, Set<List<Integer>> set){   
    // ending case   
    if(sum==target){set.add(path); return;}   
    // recursion   
    for(int i = index+1;i < n.length;i++){   
     if(n[i]+sum > target) break;   
     List<Integer> list = new ArrayList<Integer>(path);   
     list.add(n[i]);   
     dfs(n, i, target, sum+n[i], list, set);   
    }   
   }   
 }  

Notice: Since all the above solution requires sorting at first. The time complexity is O(nlogn). Space is O(n!).

Improved Way: Can I apply iterative method without using extra class (SumNode in the above code).
If I directly use List<Integer> as nodes, I need to find a way to store the sum of the list and the current index.  I could use the first element to store the sum, the second element to store the current index.

 public class Solution {  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Stack<List<Integer>> stack = new Stack<List<Integer>>();  
     Arrays.sort(num);  
     // initial list  
     List<Integer> root = new ArrayList<Integer>();  
     root.add(0);  
     root.add(-1);  
     // DFS  
     stack.push(root);  
     while(!stack.isEmpty()){  
       List<Integer> list = stack.pop();  
       // check if target found  
       if(list.get(0)==target){  
         List<Integer> path = new ArrayList<Integer>();  
         for(int i = 0;i < list.size()-2;i++)  
           path.add(list.get(i+2));  
         set.add(path);  
       }  
       // push child list  
       for(int i = list.get(1)+1;i < num.length;i++){  
         if(list.get(0)+num[i] > target) break;  
         List<Integer> path = new ArrayList<Integer>(list);  
         path.set(0, path.get(0)+num[i]);  
         path.set(1, i);  
         path.add(num[i]);  
         stack.push(path);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;   
   }  
 }  

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Naive Way: Make a recursive function to DFS on all possible combinations. And sort the entire array at first helps to keep numbers in order.

 public class Solution {  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Arrays.sort(candidates);  
     dfs(candidates, 0, target, 0, new ArrayList<Integer>(), rslt);  
     return rslt;  
   }  
   private void dfs(int[] n, int index, int target, int sum, List<Integer> path, List<List<Integer>> rslt){  
     // ending case  
     if(sum==target){rslt.add(path); return;}  
     // recursion  
     for(int i = index;i < n.length;i++){  
       if(n[i]+sum > target) break;  
       List<Integer> list = new ArrayList<Integer>(path);  
       list.add(n[i]);  
       dfs(n, i, target, sum+n[i], list, rslt);  
     }  
   }  
 }  

The corresponding iterative way is using a stack to implement DFS.

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Stack<SumNode> stack = new Stack<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     stack.push(root);  
     while(!stack.isEmpty()){  
       SumNode node = stack.pop();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else stack.push(child);  
       }  
     }  
     return rslt;  
   }  
 }  

And I though about it for a while and tried BFS on it. (Just change the stack to queue). It works. DFS and BFS are two traversal methods on this problem.

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Queue<SumNode> queue = new LinkedList<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     queue.add(root);  
     while(!queue.isEmpty()){  
       SumNode node = queue.poll();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else queue.add(child);  
       }  
     }  
     return rslt;  
   }  
 }  

Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.
For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Naive Way: Keep two pointers, let the second pointer move n step first. Then the gap between two pointers is n. Keep moving both pointers forward at same speed until second one reach the end. Then reconnect.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode removeNthFromEnd(ListNode head, int n) {  
     ListNode fake = new ListNode(0);  
     fake.next = head;  
     ListNode first = fake, second = fake;  
     // forward second by n  
     while(n-->0 && second.next!=null) second = second.next;  
     // edge case, length of linkedlist< n  
     if(n > 0){return head;}  
     // forward first and second till second reach the end  
     while(second.next!=null){  
       first = first.next;  
       second = second.next;  
     }  
     ListNode temp = first.next.next;  
     first.next = temp;  
     return fake.next;  
   }  
 }  

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2) 

Naive Way:  Use O(n^2) space list to store all 2sum Nodes. Use a map to map a 2sum to its corresponding index in 2sum list. go through each pair again to find valid four sum pairs.

 public class Solution {  
   class TwoSum{  
     int child1, child2;  
     int val;  
     TwoSum(int v, int c1, int c2){  
       this.val = v;  
       this.child1 = c1;  
       this.child2 = c2;  
     }  
   }  
   public List<List<Integer>> fourSum(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     List<TwoSum> twoSums = new ArrayList<TwoSum>();  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     // edge case  
     if(num.length < 4) return rslt;  
     // construct two sum list  
     for(int i = 0;i < num.length-1;i++)  
       for(int j = i+1;j < num.length;j++)  
         twoSums.add(new TwoSum(num[i]+num[j], i, j));  
     // sort two sum list  
     Comparator<TwoSum> comparator= new Comparator<TwoSum>(){  
       public int compare(TwoSum a, TwoSum b){  
         return a.val > b.val?1:(a.val < b.val?-1:0);  
       }  
     };  
     Collections.sort(twoSums, comparator);  
     // map two sum value with corresponding begin index in two sum list  
     int cur = 0;  
     map.put(twoSums.get(cur).val, cur);  
     for(int i = 1;i < twoSums.size();i++){  
       if(twoSums.get(i).val==twoSums.get(cur).val) continue;  
       cur = i;  
       map.put(twoSums.get(i).val, cur);  
     }  
     // find four sum  
     for(int i = 0;i < num.length-1;i++){  
       for(int j = i+1;j < num.length;j++){  
         int rest = target - num[i] - num[j];  
         if(map.containsKey(rest)){  
           int u = map.get(rest);  
           while(u < twoSums.size() && twoSums.get(u).val == rest){  
             int a = i, b = j, c = twoSums.get(u).child1, d = twoSums.get(u).child2;  
             if(a!=b && a!=c && a!=d && b!=c && b!=d && c!= d){  
               List<Integer> list = new ArrayList<Integer>();  
               list.add(num[a]);  
               list.add(num[b]);  
               list.add(num[c]);  
               list.add(num[d]);  
               Collections.sort(list);  
               set.add(list);  
             }  
             u++;  
           }  
         }  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

This is a pretty inefficient way. It doesn't quite take use of sorting.

If I get two sums as a list of number, can I apply finding two sum on that O(n^2) list using two pointer trick? It fails on the case when two sum sequence is [-4, -4, 4, 4] with target 0. Because both -4 needs to be matched with either 4 once. I cannot simply skip it after use a two sum number.

Can I sort the array first. And then, keep two pointers at begin and end. Each time, go through [begin, end] using two pointer trick like 3sum?

 public class Solution {  
   public List<List<Integer>> fourSum(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Arrays.sort(num);  
     for(int i = 0;i < num.length-3;i++){  
       if(i==0 || i> 0 && num[i]!=num[i-1]){  
       for(int j = i+1;j < num.length-2;j++){  
         if(j==i+1 || j > i+1 && num[j]!= num[j-1]){  
         int rest = target - num[i] - num[j];  
         int low = j+1, high = num.length-1;  
         while(low < high){  
           int sum = num[low] + num[high];  
           if(sum == rest){  
             List<Integer> list = new ArrayList<Integer>();  
             list.add(num[i]);  
             list.add(num[j]);  
             list.add(num[low]);  
             list.add(num[high]);  
             rslt.add(list);  
             while(high > low && num[high] == num[--high]);  
             while(high > low && num[low] == num[++low]);  
           }  
           else if(sum > rest)  
             high--;  
           else  
             low++;  
         }  
         }  
       }  
       }  
     }  
     return rslt;    
   }  
 }  

This method can be generalized to k-sum.

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Naive Way: At first, I try to use division(/) to get highest digit and mod(%) to get lowest digit and eliminate both digit once manipulated, but fail at case 10021. And then, I turn to a more brute force way. Write a sub function that get a particular digit from candidate integer. Keep compare mirror digits.

 public class Solution {  
   static final int MAX_DIGIT = 10;  
   public boolean isPalindrome(int x) {  
     // negative integer is not palindrome  
     if(x < 0) return false;  
     int low = 0, high = MAX_DIGIT;  
     // get highest digit  
     while(x < Math.pow(10,high)) high--;  
     // validate each digit pair  
     while(low < high) if(getDigit(low++, x)!=getDigit(high--, x)) return false;  
     return true;  
   }  
   private int getDigit(int n, int x){  
     // edge case, x doesn't have n digit  
     if(Math.pow(10, n) > x) return -1;  
     // edge case, n == base  
     if(n==(int)Math.pow(10,MAX_DIGIT) && x >= n) return x/n;  
     // general case  
     return (x%(int)Math.pow(10,n+1) - x%(int)Math.pow(10,n))/(int)Math.pow(10,n);  
   }  
 }  

After viewing some solution in Discuss, I found that there are some one who handles 10021 case in a correct way. I developed my own based on previous attempt.

 public class Solution {  
   static final int base = 1000000000;  
   public boolean isPalindrome(int x) {  
     // negative integer is not palindrome  
     if(x < 0) return false;  
     int i = base;  
     while(i > x) i/= 10;  
     while(i > 1){  
       if(x/i != x%10) return false;  
       x -= x/i * i;  
       x /= 10;  
       i /= 100;  
     }  
     return true;  
   }  
 }  

Improved Way: I didn't think of reverse the integer and than compare. And I think reverse an integer may incur a lot more edge case. But if you are able to deal with edge case gracefully, that's a good method. See o-1-space-o-lgn-time-java-solution-no-overflow-risk

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321 

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Naive Way:  My method is to keep getting the least valuable digit from x. This method is a good approach when I implements it. But the edge case really bothers me. I manually add edge overflow cases in three parts, which is pretty bad.

 public class Solution {  
   public int reverse(int x) {  
     // edge case  
     if(x==Integer.MIN_VALUE) return 0;  
     // negative number, convert from positive  
     if(x < 0) return -reverse(-x);  
       
     int y = 0;  
     for(int i = 10;x!=0;i *= 10){  
         
       // overflow  
       if(y > Integer.MAX_VALUE/10) return 0;  
         
       y *= 10;  
       y += (x%i)/(i/10);  
       x -= x%i;  
         
       // overflow  
       if(i==1000000000 && x!=0){  
         if(y > Integer.MAX_VALUE/10) return 0;  
         y *= 10;  
         y += x/i;  
         x = 0;  
       }  
     }  
     return y;  
   }  
 }  

Improved Way: A better way is to include as many as edge case in the main loop. Then I try to get the most valuable digit first. It turns out that it's hard to deal with edge case also.

 public class Solution {  
   static final int base = 1000000000;  
   public int reverse(int x) {  
     // edge case, overflow  
     if(x == Integer.MIN_VALUE) return 0;  
     // negative value  
     if(x < 0) return -reverse(-x);  
       
     int y = 0, highest = 1;  
     for(int i = base;i != 0;i/= 10){  
       // note down highest digit  
       if(x >= i && highest==1) highest = i;  
         
       // edge case, overflow  
       if(x/i > 2 && highest == base && i==1) return 0;  
       if(y > Integer.MAX_VALUE - x/i*(highest/i)) return 0;  
         
       y += x/i*(highest/i);  
       x -= x/i*i;  
     }  
     return y;  
   }  
 }  

Using Double or Long can simply deal with overflow, just check the result after reverse. But I don't think that's what the question is asking.

And my first approach is a correct thinking, but not being correctly manipulated. Here is a gentle way to deal with overflow edge case.

 public class Solution {  
   public int reverse(int x) {  
     // edge case  
     if(x==Integer.MIN_VALUE) return 0;  
     // negative number, convert from positive  
     if(x < 0) return -reverse(-x);  
       
     int y = 0;  
     while(x != 0){  
         
       // edge case, overflow  
       if(y > Integer.MAX_VALUE/10) return 0;  
         
       y *= 10;  
       y += x%10;  
       x /= 10;  
     }  
     return y;  
   }  
 }  

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Naive Way: Let me start from the begin, when I met some bar that is no less than current bar, I am able to determine how much water can trap from current bar to that some bar. Better use a stack to keep track of bars that are smaller than current bar.

Run time is One Pass, O(n). Space is O(n).

 public class Solution {  
   public int trap(int[] A) {  
     Stack<Integer> stack = new Stack<Integer>();  
     int sum = 0;  
     int pre = 0;  
     int i = -1;  
     while(++i < A.length){  
       if(A[i]==0){pre = 0;continue;}  
       while(!stack.isEmpty() && A[i] >= A[stack.peek()]){  
         sum += (A[stack.peek()] - pre) * (i-stack.peek()-1);  
         pre = A[stack.pop()];  
       }  
       if(!stack.isEmpty()){  
         sum += (A[i] - pre) * (i-stack.peek()-1);  
         pre = A[i];  
       }  
       stack.push(i);  
     }  
     return sum;  
   }  
 }  

Improved Way: Is there a way to make the space O(1)? Based on my previous code, the stack is not replaceable. So I cannot make up an O(1) algorithm with the stack.

Consider the bars as a whole, only the left most and right most bars will become boundaries/walls. Anything in between will take the unit place of water. This is a thinking. Let me give it a try.

The following algorithm is the implementation of my idea. Track from both ends to middle, keep increase the boundary bar, while deleting any lower bar in the middle.

 public class Solution {  
   public int trap(int[] A) {  
     int left = 0 , right = A.length-1;  
     int sum = 0;  
     int pre = 0;  
     while(left < right){  
       sum += (Math.min(A[left], A[right])-pre) * (right-left-1);  
       pre = Math.min(A[left],A[right]);  
       if(A[left] > A[right]){   
         int temp = right-1;  
         while(left < temp && A[temp] <= pre){sum-=A[temp];temp--;}  
         if(left < temp) sum -= pre;  
         right = temp;  
       }else{  
         int temp = left+1;  
         while(temp < right && A[temp] <= pre){sum-=A[temp];temp++;}  
         if(temp < right) sum -= pre;  
         left = temp;  
       }  
     }  
     return sum;  
   }  
 }  

There is a much more concise implementation java-10-lines-accepted-code-time-space-there-better-solution

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Naive Way:It seems to be another typical two pointers question. However, it is not good for us to keep replace on array A. It may overlap unused elements. Notice that A has at least n space in the backward that hasn't been used yet. Can we do two pointers trick start from the end? Will that cause overlapping on unused element, too?

Yes, we can. Consider the worst case, all elements in B are greater than all elements in A. We need to first put all elements in B into A. Will that overlap unused elements in A? No, because there are at least n space, which can hold all elements in B neatly.

 public class Solution {  
   public void merge(int A[], int m, int B[], int n) {  
     int index = n+m-1;  
     int p1 = m-1, p2 = n-1;  
     while(p1 >= 0 && p2 >= 0){  
       if(A[p1] < B[p2])  
         A[index--] = B[p2--];  
       else  
         A[index--] = A[p1--];  
     }  
     while(p1 >= 0) A[index--] = A[p1--];  
     while(p2 >= 0) A[index--] = B[p2--];  
   }  
 }  

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Naive Way: A usual way is to treat it like merging two sorted arrays.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     while(l1 != null && l2 != null){  
       if(l1.val < l2.val){  
         cur.next = l1;  
         l1 = l1.next;  
       }else{  
         cur.next = l2;  
         l2 = l2.next;  
       }  
       cur = cur.next;  
     }  
     if(l1 != null) cur.next = l1;  
     if(l2 != null) cur.next = l2;  
     return fake.next;  
   }  
 }  

Improved way: There is a better to make use a queue structured recursive method.

 public class Solution {  
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
     if(l1==null) return l2;  
     else if (l2==null) return l1;  
     if(l1.val < l2.val){  
       l1.next = mergeTwoLists(l1.next, l2);  
       return l1;  
     }else{  
       l2.next = mergeTwoLists(l1, l2.next);  
       return l2;  
     }  
   }  
 }  

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Naive Way:This question is asked on My Algorithm Course Mid-term Exam. Unfortunately, I didn't work thought it. But now, I know two methods to this question in O(nlogk) run time.

The first method is keep a heap. Push the head of each list into the heap. Pop the min from the heap and push its next into the heap. This method is an ideal way to solve the problem.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode mergeKLists(List<ListNode> lists) {  
     // edge case  
     if(lists.size()==0) return null;  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     Comparator<ListNode> c = new Comparator<ListNode>(){  
       @Override  
       public int compare(ListNode a, ListNode b){  
         if(a.val > b.val) return 1;  
         else if(a.val < b.val) return -1;  
         else return 0;  
       }  
     };  
     PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), c);  
     // initialize heap  
     for(int i = 0;i < lists.size();i++) if(lists.get(i)!=null) heap.offer(lists.get(i));  
     // pop from heap until empty  
     while(!heap.isEmpty()){  
       cur.next = heap.poll();  
       cur = cur.next;  
       if(cur.next!=null) heap.offer(cur.next);  
     }  
     return fake.next;  
   }  
 }  

Another way is great, too. Keep merge the lists two by two until there is only one list. And for merge two lists, I can use former way in Merge Two Sorted Lists.

 public class Solution {  
   public ListNode mergeKLists(List<ListNode> lists) {  
     // edge case  
     if(lists.size()==0) return null;  
     for(int i = 1;i < lists.size();i*=2)  
       for(int j = 0;j+i < lists.size();j+=2*i)  
         lists.set(j,mergeTwoSortedLists(lists.get(j), lists.get(j+i)));  
     return lists.get(0);  
   }  
   private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2){  
     if(l1==null) return l2;  
     else if (l2==null) return l1;  
     if(l1.val < l2.val){  
       l1.next = mergeTwoSortedLists(l1.next, l2);  
       return l1;  
     }else{  
       l2.next = mergeTwoSortedLists(l1, l2.next);  
       return l2;  
     }  
   }  
 }  

Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Naive Way: The question is not difficult. Write both iterative and recursive methods.

Recursive Method.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     // base case  
     if(p==null || q==null) return p==null && q==null;  
     // recursion  
     return p.val==q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);  
   }  
 }  

Iterative Method.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     // edge case  
     if(p==null || q==null) return p==null && q==null;  
     // general case, BFS  
     Queue<TreeNode> p_queue = new LinkedList<TreeNode>();  
     Queue<TreeNode> q_queue = new LinkedList<TreeNode>();  
     p_queue.offer(p);  
     q_queue.offer(q);  
     while(!p_queue.isEmpty() && !q_queue.isEmpty()){  
       TreeNode p_node = p_queue.poll();  
       TreeNode q_node = q_queue.poll();  
       if(p_node.val!=q_node.val) return false;  
       if(p_node.left!= null && q_node.left!=null){  
         p_queue.offer(p_node.left);  
         q_queue.offer(q_node.left);  
       }else if(!(p_node.left==null && q_node.left==null))  
         return false;  
       if(p_node.right!= null && q_node.right!=null){  
         p_queue.offer(p_node.right);  
         q_queue.offer(q_node.right);  
       }else if(!(p_node.right==null && q_node.right==null))  
         return false;  
     }  
     return p_queue.isEmpty() && q_queue.isEmpty();  
   }  
 }  

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Naive Way: To go through each bit using a mask will take 32 unit time. However, there is a way that runs faster, x & (x-1), which removes the right most 1 from x. For reference, see low-level-bit-hacks

 public class Solution {  
   // you need to treat n as an unsigned value  
   public int hammingWeight(int n) {  
     int count = 0;  
     while(n != 0){  
       n = n & (n-1);  
       count++;  
     }  
     return count;  
   }  
 }  

Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Naive Way: Use a HashTable to store added numbers. If I want to make add operation O(1), then find operation requires O(n) to go through the HashTable. If I want to make find operation O(1), then the add operation requires O(n) to generate all possible two sums.

add O(1), find O(n), space O(n^2)

 // add O(n), find O(1), space O(n^2)  
      Set<Integer> twoSums = new HashSet<Integer>();  
      Set<Integer> ints = new HashSet<Integer>();  
       public void add(int n){  
            Iterator<Integer> iter = ints.iterator();  
            while(iter.hasNext()){  
                 twoSums.add(iter.next()+n);  
            }  
            ints.add(n);  
       }  
       public boolean find(int n){  
            return twoSums.contains(n);  
       }  

add O(n), find O(1), space O(n)

 // add O(1), find O(n), space O(n)  
      Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
      public void add(int n){  
           if(map.containsKey(n))  
                map.put(n,map.get(n)+1);  
           else  
                map.put(n,1);  
      }  
      public boolean find(int n){  
           Iterator iter = map.entrySet().iterator();  
           while(iter.hasNext()){  
                Entry cur = (Entry)iter.next();  
                if(map.containsKey(n-(int)cur.getKey())){  
                     if(n == 2*(int)cur.getKey())  
                          return (int)cur.getValue()>=2;  
                     else  
                          return true;  
                }  
           }  
           return false;  
      }  

Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Naive Way: In Two Sum, the array is not sorted. Thus, we need extra O(n) space to store visited ones. This time, the array is sorted, leading me to think about the 3-sum method algorithm. With two pointers, we can do it in O(1) space.

 public int[] twoSum2(int numbers[], int target){  
     int[] rslt = {-1,-1};  
     int low = 0, high = numbers.length-1;  
     while(low < high){  
       if(numbers[low]+numbers[high] == target){  
         rslt[0] = low+1;  
         rslt[1] = high+1;  
         break;  
       }  
       if(numbers[low]+numbers[high] > target)  
         high--;  
       else  
         low++;  
     }  
     return rslt;
}  

Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

Naive Way: I try to draw an example like [1 2 1 3 2 1 2 1]. It turns out that for a given number h[i], whether the next position is great than h[i] or no greater than h[i] won't determine the largest capacity using h[i]. Only the last h[j] >= h[i] matters. So I tried two pointers, one from left and one from right, using two hashmap to keep track of number->position pairs.

Below code is based on that idea.

 public class Solution {  
   public int maxArea(int[] height) {  
     Map<Integer, Integer> rightMost = new HashMap<Integer,Integer>();  
     Map<Integer, Integer> leftMost = new HashMap<Integer, Integer>();  
     int left = 0, right = height.length-1;  
     int max = 0;  
     while(left < right){  
       while(left < right && leftMost.containsKey(height[left])) left++;  
       leftMost.put(height[left],left);  
       if(rightMost.containsKey(height[left])) max = Math.max(max,(right-left)*height[left]);  
       else{  
         while(left < right && height[right] < height[left]){  
           max = Math.max(max,(right-left)*height[right]);  
           rightMost.put(height[right], right);  
           right--;  
         }  
         for(int i = height[left];i <= height[right];i++)  
           rightMost.put(i,right);  
         max = Math.max(max,(right-left)*height[left]);  
       }  
     }  
     return max;  
   }  
 }  

This code has a big shortcoming in that it is not exact O(n), if two numbers are far away, say 2 and 200000, need to put into the map 200000 times. It is definitely not an ideal solution.

Improved Way: I finally realize that when a number as large as 200000 was met on the right, it matches almost all the left numbers. Right pointer don't need to move any more, Which means only the minimum of left and right should move! And integrate with the idea that only left and right boundaries matter. I finally come up with this code. Real O(n).

 public class Solution {  
   public int maxArea(int[] height) {  
     int left = 0, right = height.length-1;  
     int max = 0;  
     while(left < right){  
       max = Math.max(max, (right-left)*Math.min(height[left],height[right]));  
       if(height[left] < height[right])  
         left++;  
       else  
         right--;  
     }  
     return max;  
   }  
 }  

Rotate Imag

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

Naive Way: To do it in-place, need to start from a point, find its corresponding new position, and then start with the new position, find its corresponding position...

The range of two index pointers is important.

 public class Solution {  
   public void rotate(int[][] matrix) {  
     int n = matrix.length;  
     for(int i = 0;i < n-1;i++){  
       for(int j = i;j < n-1-i;j++){  
         int count = 0;  
         int x = i,y = j;  
         int pre = matrix[x][y];  
         while(count++ < 4){  
           int temp = matrix[y][n-1-x];  
           matrix[y][n-1-x] = pre;  
           int temp_x = x;  
           x = y;  
           y = n-1-temp_x;  
           pre = temp;  
         }  
       }  
     }  
     return;  
   }  
 }  

Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Naive Way: The problem said "You should pack your words in a greedy approach". So I will pack the words greedily. Grad as many words as I can each time to form a line. To calculate the space, use an extra var to hold the remaining space after evenly distributes. For the last column, could assign an extra check.

Combining one word case and the last line case is feasible.

 public class Solution {  
   public List<String> fullJustify(String[] words, int L) {  
     List<String> list = new ArrayList<String>();  
     int i = 0;  
     while(i < words.length){  
       int j = i;  
       int len = 0;  
       // grab as many words as I can  
       while(j < words.length && len+ (j-i) + words[j].length() <= L) len += words[j++].length();  
       // # of space need to be inserted between each word is j==i?0:(L-len)/(j-i)  
       int space = j<=i+1?0:(L-len)/(j-i-1);  
       // # of space remained, L - len - space*(j-i);  
       int remain = L -len- space*(j-i-1);  
       // construct a line  
       StringBuilder s = new StringBuilder();  
       // one word case & last line case  
       if(j==words.length || j<=i+1){  
         for(int t = i;t < j;t++){  
           s.append(words[t]);  
           if(t!=j-1) s.append(" ");  
         }  
         remain += space*(j-i-1)-(j-i-1);  
         for(int t = 0;t < remain;t++) s.append(" ");  
       }else{  
         // general case  
         for(int t = i;t < j;t++,remain--){  
           s.append(words[t]);  
           if(t!=j-1) for(int u = 0;u < space;u++) s.append(" ");  
           if(remain > 0) s.append(" ");  
         }  
       }  
       // add line  
       list.add(s.toString());  
       i = j;  
     }  
     return list;  
   }  
 }  

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).
Follow up:
If this function is called many times, how would you optimize it?

Naive Way:Need to use another integer to store the reversed bits. Traversal target from low to high,  construct result from high to low.
The key here is to use ">>>" instead of ">>"
1000 >> 1 becomes 1100
1000 >>>1 becomes 0100

 public class Solution {  
   // you need treat n as an unsigned value  
   public int reverseBits(int n) {  
     int m = 0;  
     for(int i = 0;i < 32;i++)  
       if((n & (0x00000001 << i)) != 0) m |= (0x80000000 >>> i);  
     return m;  
   }  
 }  

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.


Naive Way:  Use a stack would be straightforward. But it's O(n) space.

 public class Solution {  
   public boolean isValid(String s) {  
     Stack<Integer> stack = new Stack<Integer>();  
     for(int i = 0;i < s.length();i++){  
       if(isLeft(s.charAt(i))) stack.push(i);  
       else if(!stack.isEmpty() && s.charAt(stack.peek())== opposite(s.charAt(i))) stack.pop();  
       else return false;  
     }  
     return stack.isEmpty();  
   }  
   private boolean isLeft(char c){  
     return c=='(' || c=='{' || c =='[';  
   }  
   private char opposite(char c){  
     if(c==')') return '(';  
     if(c=='}') return '{';  
     else return '[';  
   }  
 }  

I know if there were only one type of parentheses, it can be done in O(1). When there are multiple parentheses, some one argue that for the reason of Context Free Grammar, It can not be done in O(1).

Improved Way: It would be better to use a Hashmap to map left parentheses to right parentheses.

 public class Solution {  
   private static final Map<Character, Character> map = new HashMap<Character, Character>(){{  
     put('(',')');  
     put('{','}');  
     put('[',']');  
   }};  
   public boolean isValid(String s) {  
     Stack<Integer> stack = new Stack<Integer>();  
     for(int i = 0;i < s.length();i++){  
       if(map.containsKey(s.charAt(i))) stack.push(i);  
       else if(!stack.isEmpty() && map.get(s.charAt(stack.peek()))==s.charAt(i)) stack.pop();  
       else return false;  
     }  
     return stack.isEmpty();  
   }  
 }