Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".

My Thinking: This question only allows to add characters in the front. The resulting palindrome  might not be the optimal result.

For example "aabcb" should return "bcbaabcb" instead of "aabcbaa".

But this is a misleading. Solve for the optimal result will give you two cases. One is adding in the front, the other is adding in the back. We just pick the first one as the result.

Back to the question. Longest Palindromic Substring already gives a way to get the longest palindrome substring for each character position. Based on the array, we can extend the longest palindrome substring and get the optimal palindrome. But that might not be adding in the front. It doesn't matter. We should extend the longest palindrome that is nearest to position 0.

For example, "aabcb"->"#a#a#b#c#b#"
                                        12321214121
character 'c' has the longest palindrome coverage 4, but it's coverage does not cover position 0.

The largest coverage covering position 0 is the '#' between two 'a'. That's where we should extend from.

 public class Solution {  
   public String shortestPalindrome(String s) {  
     // preprocessing  
     if(s == null || s.length()==0) return s;  
     s = preProcess(s);  
       
     // get longest palindrome substring  
     int[] range = new int[s.length()];  
     int pivot = 0;  
     range[0] = 1;  
     for(int i = 1;i < s.length();i++){  
       if(range[pivot]+pivot > i){  
         if(range[pivot] + pivot > range[2*pivot-i] + i)  
           range[i] = range[2*pivot-i];  
         else  
           range[i] = range[pivot]+pivot-i;  
       }  
         
       while(range[i]+i < s.length() && i-range[i] >= 0 && s.charAt(i+range[i])==s.charAt(i-range[i])) range[i]++;  
   
       if(range[pivot]+pivot < range[i]+i) pivot = i;  
     }  
       
     // extend based on the longest palindrome substring  
     while(pivot-(range[pivot]-1)!=0) pivot--;  
     s = reverse(s.substring(pivot+range[pivot], s.length())) + s;  
       
     // postprocessing  
     return postProcess(s);  
       
   }  
     
   private String reverse(String s){  
     return new StringBuilder(s).reverse().toString();  
   }  
     
   private String postProcess(String s){  
     StringBuilder rslt = new StringBuilder();  
     for(int i = 0;i < s.length();i++)  
       if(s.charAt(i)!='#') rslt.append(s.charAt(i));  
     return rslt.toString();  
   }  
     
   private String preProcess(String s){  
     StringBuilder rslt = new StringBuilder();  
     for(int i = 0;i < s.length();i++){  
       if(i==0) rslt.append("#");  
       rslt.append(s.charAt(i));  
       rslt.append("#");  
     }  
     return rslt.toString();  
   }  
 }  

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

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

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.

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

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

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

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

Rotate Array

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Naive Way: 要想三种方法。
1.最简单的一种就是用一个新数组去装载新的数组然后再复制回去。这种方法需要O(n) space，算法复杂度是O(n)。实际做的时候还发现k会出现比n大的情况。

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     int temp[] = new int[nums.length];  
     for(int i = 0;i < nums.length;i++)  
       temp[i] = i < k? nums[nums.length-k+i]:nums[i-k];  
     for(int i = 0;i < nums.length;i++)  
       nums[i] = temp[i];  
   }  
 }  

在原来的方法上想，优化一下可以使空间可以降到O(min(k,n-k))

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     if(nums.length-k > k){  
       int temp[] = new int[k];  
       for(int i = 0;i < k;i++)  
         temp[i] = nums[nums.length-k+i];  
       for(int i = nums.length-1;i >= k;i--)  
         nums[i] = nums[i-k];  
       for(int i = 0;i < k;i++)  
         nums[i] = temp[i];  
     }else{  
       int temp[] = new int[nums.length-k];  
       for(int i = 0;i < temp.length;i++)  
         temp[i] = nums[i];  
       for(int i = 0;i < k;i++)  
         nums[i] = nums[i+nums.length-k];  
       for(int i = 0;i < nums.length-k;i++)  
         nums[i+k] = temp[i];  
     }  
   }  
 }  

2. 可以模仿rotate linked list 的插值法，不过在数组上插值，每一次就要移动 n 位了，这样就得到一个算法复杂度为O(nk), space O(1) 的方法。但是这样会超时。

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     for(int i = 0;i < k;i++){  
       int temp = nums[nums.length-k+i];  
       for(int j = nums.length-k+i;j >= i+1;j--)  
         nums[j] = nums[j-1];  
       nums[i] = temp;  
     }  
   }  
 }  

3.可不可以仅通过swap来实现O(1)。 好像可以通过recursive的greedy算法实现。
于是写了这个O(1) space的算法，弄了好久。核心思想是在不产生overlap的情况下，尽可能多的交换， 然后剩下的没有进行交换的则建立新的分割，由下一个recursive的函数进行交换。

算法复杂度是O(n) （每个数最多被交换两次）

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     k %= nums.length;  
     rotate(nums,0,nums.length-k-1);  
   }  
   /*  
   * begin is where the sequence to be processed starts  
   * end is the cut where separates the two slices of the array  
   * nums = [<processed>,<       to be processed         >]  
   *                  |                        |   
   *                  <begin, end>, <end+1, nums.length-1>  
   * Afterwards:        <processed >, <  to be processed    >   
   */  
   private void rotate(int[] nums, int begin, int end){  
     // base case  
     if(end == nums.length-1) return;  
     // recursive  
     int k = Math.min(end-begin+1, nums.length-1-end);  
     for(int i = 0; i < k;i++)  
       swap(nums, begin+i, end+1+i);  
     if(k==end-begin+1)  
       rotate(nums, begin+k, end+k);  
     else  
       rotate(nums, begin+k, nums.length-k-1);  
   }  
   private void swap(int[] nums, int index1, int index2){  
     int temp = nums[index1];  
     nums[index1] = nums[index2];  
     nums[index2] = temp;  
   }  
 }  

Improved Way:在Discuss里看到了两个很好的方法。

第一个是
mjsaber的，不得不说他这个做法实在太聪明了。先把整个数组头尾互换，此时要交换的两部分已经处于各自半区了，但是顺序是反的，然后在内部翻转。这个方法是主流的方法。

 public class Solution {  
   public void rotate(int[] nums, int k) {  
     if (nums == null || nums.length == 0) {  
       return;  
     }  
     k = k % nums.length;  
     reverse(nums, 0, nums.length-k-1);  
     reverse(nums, nums.length-k, nums.length-1);  
     reverse(nums, 0, nums.length-1);  
   }  
   private void reverse(int[] num, int left, int right) {  
     while (left < right) {  
       int t = num[left];  
       num[left] = num[right];  
       num[right] = t;  
       left++;  
       right--;  
     }  
   }  
 }  

第二个是 xcv58的，采用从后往前换，每次换好一个找当前这个要换的位置。

 public void rotate(int nums[], int n, int k) {  
   for (int i = 0, j = k % n, previous = nums[i], anchor = i, count = n; count > 0; count--, j = (i + k) % n) {  
     int tmp = nums[j];  
     nums[j] = previous;  
     previous = tmp;  
     if ((i = j) == anchor) {  
       i = (i + 1) % n;  
       previous = nums[i];  
       anchor = i;  
     }  
   }  
 }  

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".


Naive Way:我第一次做的时候以为3是个常数呢。这种zigzag scan 有规律可循啊，只要找到index的映射规律，就可以一次scan 实现。首先例子是一个nRows = 3的，写一个nRows = 4的。

P         I         N
A    L S      I  G
Y A    H R
P         I

首先看第一行，前一个和后一个的间隔是 2*nRows - 1(折点）-1(起点) -1(终点)，如果是步长就还要+1算上自己，那么步长就是 2*nRows-2，这个规律是普适的。
然后看第二行，前一个和中间那个的步长是 2*(nRows-1)-2，这个很好理解就是 减少了两个点。 注意到，竖直方向上前一个和竖直方向上后一个的步长还是 2*nRows-2，相当于之前分析部分起点+1, 终点+1。所以可以把中间部分的单独列出来考虑。
第三行就显而易见，竖直方向上第一个和中间的步长是2*(nRows-2)-2，因为又减少了两个。
第四行的情况和第一行一样。

总结一下就是，基本步长为2*nRows-2。如果不是第一行和最后一行，就要增加中间点，它和前一个竖直方向上的步长是 2*(nRows-index)-2，index是行的序号。还有就是nRows=1时，步长为0，不能统一，单独步长。

算法复杂度O(n), space O(n)。 一次扫描。

 public class Solution {  
   public String convert(String s, int nRows) {  
     StringBuilder str = new StringBuilder();  
     for(int i = 0;i < nRows;i++){  
       int j = i;  
       while(j < s.length()){  
         str.append(s.charAt(j));  
         if(i!=0 && i!=nRows-1 && j+2*(nRows-i)-2 < s.length())  
           str.append(s.charAt(j+2*(nRows-i)-2));  
         j += nRows==1?1:(2*nRows-2);  
       }  
     }  
     return str.toString();  
   }  
 }  

Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?


Naive Way:  和Reverse Words in String不同的是，这次的String是标准格式。但这次严格要求O(1)的space。因为没钱买，所以看了一下问答部分，这次它将String 改成了 char[],返回值是void。这样才能实现O(1) space，因为String是immutable的。

我想到一个简单的办法，用一头一尾交换先将整个char[] 翻转，然后对每一个单词再作内部翻转，这样就可以实现O(1) space，但是需要扫两遍。

 public class Solution{  
   public static void main(String args[]){  
     char[] s = {'t','h','e',' ','s','k','y',' ','i','s',' ','b','l','u','e'};  
     Solution ss = new Solution();  
     ss.reverseWords(s);  
     for(int i = 0;i < s.length;i++)  
       System.out.print(s[i] + " ");  
     System.out.println();  
   }  
   public void reverseWords(char[] s){  
     reverseWords(s,0,s.length-1);  
     for(int i = 0, j = 0;i <= s.length;i++){  
       if(i==s.length || s[i] == ' '){  
         reverseWords(s,j,i-1);  
         j = i+1;  
       }  
     }  
   }  
   private void reverseWords(char[] s, int begin, int end){  
     while(begin < end){  
       char c = s[begin];  
       s[begin] = s[end];  
       s[end] = c;  
       begin++;  
       end--;  
     }  
   }  
 }  

Reverse Words in a String

Reverse Words in a String

 

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".

Naive Way: 如果能使用String.split()就会很方便。

如答案所说，使用String.split() 是需要两次扫描的。如果从后往前扫String，就只需要一次扫面。

 public class Solution {  
   public String reverseWords(String s) {  
     StringBuilder rslt = new StringBuilder();  
     String[] str = s.split(" ");  
     for(int i = str.length-1;i >= 0;i--){  
       if(i!=str.length-1 && str[i].length()!=0) rslt.append(" ");  
       rslt.append(str[i]);  
     }  
     return rslt.toString();  
   }  
 }   

这次从后往前扫，只需要一次。

 public class Solution {  
   public String reverseWords(String s) {  
     StringBuilder rslt = new StringBuilder();  
     int i = s.length(), j = s.length();  
     while(--i >= -1){  
       if(i==-1 || s.charAt(i) == ' '){  
         if(i+1!=j && rslt.length()!=0) rslt.append(" ");  
         rslt.append(s.substring(i+1,j));  
         j = i;  
       }  
     }  
     return rslt.toString();  
   }  
 }  

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).


Naive Way: brute force 的方法将是每一个字符的遍历，看它所引领的字符串是否为字典所组成。假设|S| = n, |L| = m, |L[0]| = k，这样的算法复杂度是O(nm)。

而我的基本的想法是隔着一个单词长度的遍历，用一个queue控制进出，然后用一个map装入L的信息，一旦queue.size() == L.length 说明找到一个match。

 如果出现这种情况 L:["foo","bar","arf"...]，说明一个substring即使在字典中找到，也不可以一个单词一个单词的向后递增。

假设每个单词长度是k，任然可以用上述方法，需要为每一个间隔都设置一个queue和一个map。然后每个间隔单独执行以上算法，这样就需要k个queue和k各map。算法复杂度是O(n)。
我觉得这个算法复杂度真心足够了。

有一个容易出错的地方是当map不包含当前word时，可能queue出来的那个正好等于当前word，此时，要做的就是不改变map，把当前word推进queue，然后queue再排出最前面的word。

算法复杂度是O(n), space O(km)

 public class Solution {  
   public List<Integer> findSubstring(String S, String[] L) {  
     List<Integer> rslt = new ArrayList<Integer>();  
     // edge case  
     if(L.length==0) return rslt;  
     // initialize k queues and k maps  
     int k = L[0].length();  
     List<Queue<String>> queues = new ArrayList<Queue<String>>();  
     List<Map<String, Integer>> maps = new ArrayList<Map<String, Integer>>();  
     Map<String, Integer> map_temp = new HashMap<String, Integer>();  
     for(int i = 0;i < L.length;i++) setMap(map_temp, L[i]);  
     for(int i = 0;i < k;i++) queues.add(new LinkedList<String>());  
     for(int i = 0;i < k;i++) maps.add(new HashMap<String, Integer>(map_temp));  
     // go though S  
     for(int i = 0;i <= S.length()-k;i++){  
       Queue<String> queue = queues.get(i%k);  
       Map<String, Integer> map = maps.get(i%k);   
       String s = S.substring(i,i+k);  
       if(map.containsKey(s)){  
         queue.add(s);  
         map.put(s,map.get(s)-1);  
         if(map.get(s)==0) map.remove(s);  
       }else{  
         if(!queue.isEmpty()){  
           if(s.equals(queue.peek())) // when the word to be poll == the word to be add  
             queue.add(queue.poll()); // don't need to modify map  
           else  
             while(!queue.isEmpty()) setMap(map, queue.poll());  
         }  
       }  
       // find a match  
       if(queue.size()==L.length){  
         rslt.add(i-(L.length-1)*k);  
         setMap(map,queue.poll());  
       }  
     }  
     return rslt;  
   }  
   private void setMap(Map<String, Integer> map, String s){  
     if(!map.containsKey(s))  
       map.put(s,1);  
     else  
       map.put(s,map.get(s)+1);  
     return;  
   }  
 }  

Improved Way: 我看了https://oj.leetcode.com/discuss/20151/an-o-n-solution-with-detailed-explanation这个算法后发现queue完全可以用一个变量来代替，记录长度即可。

 public class Solution {  
   public List<Integer> findSubstring(String S, String[] L) {  
     List<Integer> rslt = new ArrayList<Integer>();  
     // edge case  
     if(L.length==0) return rslt;  
     // initialize k queues and k maps  
     int k = L[0].length();  
     int queues[] = new int[k];  
     List<Map<String, Integer>> maps = new ArrayList<Map<String, Integer>>();  
     Map<String, Integer> map_temp = new HashMap<String, Integer>();  
     for(int i = 0;i < L.length;i++) setMap(map_temp, L[i]);  
     for(int i = 0;i < k;i++) queues[i] = 0;  
     for(int i = 0;i < k;i++) maps.add(new HashMap<String, Integer>(map_temp));  
     // go though S  
     for(int i = 0;i <= S.length()-k;i++){  
       int queue = queues[i%k];  
       Map<String, Integer> map = maps.get(i%k);   
       String s = S.substring(i,i+k);  
       if(map.containsKey(s)){  
         queue++;  
         map.put(s,map.get(s)-1);  
         if(map.get(s)==0) map.remove(s);  
         // find a match  
         if(queue==L.length){  
           rslt.add(i-(queue-1)*k);  
           setMap(map, S.substring(i-k*(queue-1),i-k*(queue-1)+k));  
           queue--;  
         }  
       }else{  
         if(queue > 0){  
           if(!s.equals(S.substring(i-k*queue,i-k*queue+k)))  
             while(queue > 0){  
               setMap(map, S.substring(i-k*queue,i-k*queue+k));  
               queue--;  
             }  
         }  
       }  
       queues[i%k] = queue;  
     }  
     return rslt;  
   }  
   private void setMap(Map<String, Integer> map, String s){  
     if(!map.containsKey(s))  
       map.put(s,1);  
     else  
       map.put(s,map.get(s)+1);  
     return;  
   }  
 }  

Plus One

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.

 

Naive Way: 有没有可能面试官问这道题。

 

 public class Solution {
    public int[] plusOne(int[] digits) {
        int[] rslt;
        boolean carry = true;
        for(int i = digits.length-1;i >=0;i--){
            int v = digits[i]+(carry?1:0);
            carry = v > 9;
            v %= 10;
            digits[i] = v;
        }
        if(carry){
            rslt = new int[digits.length+1];
            rslt[0] = 1;
            for(int i = 1;i < rslt.length;i++) rslt[i] = digits[i-1];
        }else{
            rslt = digits;
        }       
        return rslt;
    }
}

Next Permutation

Next Permutation

 

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1



Naive Way: 审题：1.recursion 2. in-place
是在一个数组上 in-place 进行的，那么就只有 覆盖原来的(overlap) 和 交换两个数(swap) 。
通过探讨它的原理我发现可以这样找，

1.从后往前遍历，应该是递增（从后往前）的，找到第一个非递增。

2.那个点就是要升位一个的点 t，在刚才来的路上找到比该数大且最接近的数 s，用该数 s 替代它（升位）。

3.后面的部分需要是从前往后看递增的，而之前来的路上一切都是递减的，所以倒过来写就可以了，相当于两头交换。

4.但是还有一个数要处理的就是 t 这个数本身，可以在交换好后，从 s 所在位置往后遍历一遍插入对应的位置。

实际做的时候发现第4步是多余的，因为交换了 t 和 s 的位置后，并不会打乱原来递减的顺序。还有一点就是找 s 的位置一定要找相同差值下最后面的位置，比如两个3，就要取后面的3，因为要保持后半部分的递减性。

算法复杂度O(n), space O(1)。

public class Solution {
    public void nextPermutation(int[] num) {
        int t,s;
        int i = num.length-1;
        while(i > 0 && num[i-1] >= num[i]) i--;
        if(i > 0){
            t = i-1;
            // search for nearest value larger than num[t] in num[i~length]
            s = i;
            for(int j = i;j < num.length;j++)
                if(num[j] > num[t] && num[j]-num[t] <= num[s]-num[t])
                    s = j;
            // swap position t and s
            num[t] = num[s] + num[t];
            num[s] = num[t] - num[s];
            num[t] = num[t] - num[s];
        }
        swapHeadAndTail(num, i, num.length-1);
        return;
    }
    
    private void swapHeadAndTail(int[] num, int begin, int end){
        while(begin < end){
            num[begin] = num[end] + num[begin];
            num[end] = num[begin] - num[end];
            num[begin] = num[begin] - num[end];
            begin++;
            end--;
        }
        return;
    }
}


以下是我第一次写的，应该当时不会写，是抄的。

public class Solution {
    public void nextPermutation(int[] num) {
        int i = num.length-1;
        int j;
        while(i > 0){
            if(num[i] > num[i-1])
                break;
            i--;
        }
        if(i != 0){
            for(j = i;j < num.length;j++)
                if(num[j] <= num[i-1])
                    break;
            swap(num, i-1, j-1);
        }
           
        reverse(num, i, num.length-1);
    }
   
    private void reverse(int[] A, int begin, int end){
        for(int i = begin;i <= (end+begin)/2;i++)
            swap(A,i,end+begin-i);
    }
   
    private void swap(int[] A, int a, int b){
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
       
}

Maximal Rectangle

Maximal Rectangle

 

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 

Naive Way: brute force的方法，对每一个点都遍历O(n^2)求出最大的长方形，算法复杂度是O(n^3)。由于有了Largest Rectangle in Histogram 的解法是O(n)，可以把矩阵从上到下扫一遍，得到n组Histogram的数据，每一组用上面的方法算最大rectangle，就可以实现O(n^2)的算法复杂度。

 

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        if(matrix.length==0){return max;}
        int height[] = new int[matrix[0].length];
        for(int i = 0;i < matrix.length;i++){
            for(int j = 0;j < matrix[i].length;j++){
                int t = height[j]==0?0:height[j]-1;
                while(i+t < matrix.length && matrix[i+t][j]=='1') t++;
                height[j] = t;
            }
            max = Math.max(max,largestRectangleArea(height));
        }
        return max;
    }
    
    public int largestRectangleArea(int[] height) {
        int largest = 0;
        int i;
        Stack<Integer> stack = new Stack<Integer>();
        // forward
        i = 0;
        while(i < height.length){
            if(!stack.isEmpty() && height[i] < height[stack.peek()])
                largest = Math.max(largest, height[stack.pop()]*(i-(stack.isEmpty()?-1:stack.peek())-1));
            else
                stack.push(i++);
        }
        // backward
        while(!stack.isEmpty()){
            largest = Math.max(largest, height[stack.pop()] * (i-(stack.isEmpty()?-1:stack.peek())-1));
        }
        return largest;
    }
}

 

 

Improved Way: 这样做法算是比较普遍的做法。在Discuss里还有一种DP的做法，也是O(n^2)，颇受好评。https://oj.leetcode.com/discuss/20240/share-my-dp-solution

 

基本逻辑为：

left[i][j] // the left most position with '1' in row i connected with position[i][j]

right[i][j] // the right most position with '1' in row i connected with position[i][j] 

height[i][j] // current height in column j for position[i][j]

 

left[i][j] = matrix[i][j] =='1'? max(leftMostZeroPosition, left[i-1][j]): 0;

right[i][j] = matrix[i][j] =='1'?min(rightMostZeroPosition, right[i-1][j]):0;

height[i][j] = matrix[i][j] =='1'?height[i-1][j]+1:0;

area[i][j] = height[i][j] *( right[i][j] - left[i][j]);

所有2D array都可以用1D array表示。

 

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        int n = matrix.length;
        if(n==0){return max;}
        int m = matrix[0].length;
        int h[] = new int[m];
        int l[] = new int[m];
        int r[] = new int[m];
        Arrays.fill(r, m);
        for(int i = 0;i < n;i++){
            int curLeft = 0, curRight = m;
            for(int j = 0;j < m;j++){
                l[j] = matrix[i][j]=='1'?Math.max(curLeft,l[j]):0;
                curLeft = matrix[i][j]=='1'?curLeft:j+1;
                
                r[m-1-j] = matrix[i][m-1-j]=='1'?Math.min(curRight,r[m-1-j]):m;
                curRight = matrix[i][m-1-j]=='1'?curRight:m-1-j;
                
                h[j] = matrix[i][j] =='1'?h[j]+1:0;
            }
            
            for(int j = 0;j < m;j++)
                max = Math.max(max, h[j] * (r[j]-l[j]));
        }
        return max;
    }
}

 

Math.max(curLeft,l[j]) 这一个逻辑使得当前最右边为1的位置与上一层保持一致性。

 

在GeeksforGeeks上有一个更容易懂的DP的做法，不过是正方形的。