Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Naive Thinking: It seems this question is a typical two-pointer question. My idea is to keep a right boundary pointer and a left boundary pointer, keep sum up everything between two boundaries and move left boundary pointer and right pointer accordingly. One thing to be notice is that the left pointer needs to be checked if it can be moved forward each times right pointer finish its extension.

Run time is O(n).

 public class Solution {  
   public int minSubArrayLen(int s, int[] nums) {  
     int left = 0;  
     int right = 0;  
     int sum = 0;  
     int leng = 0;  
     int min_leng = nums.length+1;  
     while(right < nums.length){  
       // extend right boundary  
       while(sum < s && right < nums.length){  
         sum += nums[right++];  
         leng++;  
       }  
       if(sum >= s && leng < min_leng) min_leng = leng;  
         
       // extend left boundary  
       do{  
         sum -= nums[left++];  
         leng--;  
         if(sum >= s && leng < min_leng) min_leng = leng;  
       }while(sum >= s && left < right);  
     }  
     return min_leng==nums.length+1?0:min_leng;  
   }  
 }  

The interesting part is the O(nlogn) run time solution. Even the run time is not efficient, it is still great practice to think it differently.

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;  
   }  
 }  

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;  
   }  
 }  

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();  
   }  
 }  

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

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;  
     }  
   }  
 }  

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;  
   }  
 }  

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

Naive Way: Keep two pointers starting from both beginning and end, check equality of two valid characters.

 public class Solution {  
   public boolean isPalindrome(String s) {  
     s = s.toLowerCase();  
     int begin = 0, end = s.length()-1;  
     while(begin < end){  
       while(!isAlphanumeric(s.charAt(begin)) && begin < end) begin++;  
       while(!isAlphanumeric(s.charAt(end)) && begin < end) end--;  
       if(s.charAt(begin)!= s.charAt(end)) return false;  
       begin++;  
       end--;  
     }  
     return true;  
   }  
   public boolean isAlphanumeric(char c){  
     return c >= '0' && c <='9' || c >= 'a' && c <= 'z';  
   }  
 }  

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Naive Way: A straightforward way is to use two head pointers to carry the list with all nodes less than x and the list with all nodes greater or equal to x. And that's O(1) space. Reset the tail of the second list may be ignored!

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode partition(ListNode head, int x) {  
     ListNode less = new ListNode(0);  
     ListNode noLess = new ListNode(0);  
     ListNode p1 = less;  
     ListNode p2 = noLess;  
     for(ListNode cur = head;cur!=null;cur = cur.next){  
       if(cur.val < x){  
         p1.next = cur;  
         p1 = p1.next;  
       }else{  
         p2.next = cur;  
         p2 = p2.next;  
       }  
     }  
     p2.next = null;  
     p1.next = noLess.next;  
     return less.next;  
   }  
 }  

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

Naive Way: I think this question is among the highest level questions for using Two Pointers. The question generally means there is an array with 0,1,2s with no order, we are going to grab all 0s first, and then all 1s and then all 2s and set them in the original array.
It would be simple if there is only 0s and 1s. We can use the Two Pointers way, use a pointer to denote current position, another for increment index. Each we come across a 0, set num[current++] = 0, and then set the remaining to be 1.
Considering the same approach, we set a pointer for 0, a pointer for 1, then the remaining positions will be 2. Each time we come across a 0, set num[pointer0++] = 0, and pointer1++. Each time we come across a 1, set pointer1++. And the final cut of the array will be [0,pointer0]->0, [pointer1,pointer1]->1, [pointer1, pointer2]->2.

 public class Solution {  
   public void sortColors(int[] A) {  
     int p0 = 0, p1 = 0;  
     for(int i = 0;i < A.length;i++){  
       if(A[i] == 0){  
         A[p0++] = 0;  
         p1++;  
       }  
       if(A[i] == 1)  
         p1++;  
     }  
     for(int i = p0;i < p1;i++) A[i] = 1;  
     for(int i = p1;i < A.length;i++) A[i] = 2;  
   }  
 }  

The above solution achieves O(1) space and O(n) time complexity, which is good given this problem.
However, the highest level for doing this question is not only achieve best space and run time, but also achieve best in algorithm level. Is there any difference between O(5n) and O(200n)? Is is better if we can scan it once to get same effect of scanning twice.

In the above solution, we actually scan the entire array twice. There is an obvious redundancy that we didn't fully make use of the core of two pointer-> cover/replace. Use a valid value to replace the incorrect value. Can we also write the array when encountering 1s and 2s?

 public class Solution {  
   public void sortColors(int[] A) {  
     int p[] = new int[3];  
     for(int i = 0;i < A.length;i++){  
       if(A[i] == 2){  
         A[p[2]++] = 2;  
       }else if(A[i] == 1){  
         A[p[2]++] = 2;  
         A[p[1]++] = 1;  
       }else{  
         A[p[2]++] = 2;  
         A[p[1]++] = 1;  
         A[p[0]++] = 0;  
       }  
     }  
   }  
 }  

And the solution can be generalized to k colors.

 public class Solution {  
   public void sortColors(int[] A) {  
     int k = 3;  
     int p[] = new int[k];  
     for(int i = 0;i < A.length;i++){  
       int t = A[i];  
       for(int j = k-1; j >= t;j--)  
         A[p[j]++] = j;  
     }  
   }  
 }  

Improved Way: Also, there is another solution that is able to achieve sort color in one pass. It uses swapping. And since it's only 0,1,2. Swapping can be done by simple assign value.

 public class Solution {  
   public void sortColors(int[] A) {  
     int p0 = 0, p1 = 0, p2 = A.length-1;  
     while(p1 <= p2){  
       if(A[p2]==2)  
         p2--;  
       else{  
         if(A[p1]==2)  
           swap(A, p1, p2);  
         else if(A[p1]==0)  
           swap(A, p0++, p1++);  
         else  
           p1++;  
       }  
     }  
   }  
   private void swap(int[] A, int x1, int x2){  
     int temp = A[x1];  
     A[x1] = A[x2];  
     A[x2] = temp;  
   }  
 }  

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Naive Way:时间复杂度的要求决定了只能是merge sort, quick sort 或者用 heap。空间复杂度先排除heap。Quick sort不熟，先试merge sort。merge sort能否只用O(1) space？好像是可以的。

写了N久终于写完了。用一快一慢两个指针引领要被merge的部分，merge函数需要在末尾清零（null），主函数需要用一个指针标记剩下的部分，以便前面部分merge完以后接上。

 /**  
  * Definition for singly-linked list.  
  * class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode sortList(ListNode head) {  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake, fast = fake, slow = fake;  
     fake.next = head;  
     // get the length of list  
     int length = 0;  
     while(cur.next!=null){  
       length++;  
       cur = cur.next;  
     }  
     for(int step = 1;step < length;step*=2){  
       cur = fake;  
       while(cur.next!=null){  
         slow = cur.next;  
         fast = cur.next;  
         int i = 0;  
         // find correct merge starting position  
         while(fast.next!=null && i < step){fast = fast.next; i++;}  
         if(i!=step) break;  
         ListNode temp = fast;  
         i = 0;  
         while(temp!=null && i < step){temp = temp.next; i++;}  
         // merge two lists  
         cur.next = merge(slow, fast, step);  
         // connect with remaining nodes  
         i = 0;  
         while(i < 2*step && cur.next!=null){cur = cur.next;i++;}  
         cur.next = temp;  
       }  
     }  
     return fake.next;  
   }  
   private ListNode merge(ListNode a, ListNode b, int len){  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     int i = 0,j = 0;  
     while(i < len && j < len && a!=null && b!=null){  
       if(a.val < b.val){  
         cur.next = a;  
         a = a.next;  
         i++;  
       }else{  
         cur.next = b;  
         b = b.next;  
         j++;  
       }  
       cur = cur.next;  
     }  
     while(i < len && a!=null){  
       cur.next = a;  
       a = a.next;  
       i++;  
       cur = cur.next;  
     }  
     while(j < len && b!=null){  
       cur.next = b;  
       b = b.next;  
       j++;  
       cur = cur.next;  
     }  
     cur.next = null;  
     return fake.next;  
   }  
 }  

Improved Way:看到Discuss里很多人都是 大的merge  call 小的merge，那样就会造成一个stack的空间使用，就不是O(1)的了，要实现O(1)，必须从小的往大的写，这样才不会同时进行多个merge。

一些提升的地方：

有一个人用Bit 运算移位来实现step*2，这样挺好的。

有一个人将获取slow, 和fast的位置写成单独的函数，这样主函数就会清晰很多。

最重要的问题：Quick Sort 是否可以写成O(1)的关于链表的。从算法的流程上讲是可以的，先对整个list 进行左右交换，然后对前一半和后一半分别进行左右交换，这样下来应该可以不适用额外空间。