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

House Robber II

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Refer from House Robber I
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

My Thinkings:

The only difference is it's a circle now instead of a straight line. The last one cant be robbed if the first one has been robbed. If I am going to use the same Dynamic Programming Process, maintaining an array to store current optimized robbery status, I can tell if the first house has been robbed or not from if(opt[1] == 0). However, I cant control the robber not to rob house 1 since opt[1] will always equal to the value in the first house.

That seems to stop me from considering it a DP process. Then I came up with a more mathematics thought-- each time spin the house value by one step, calling DP solution on each new array. Now, I realize how stupid I am. In this way, I still didn't solve the circling thing-- how to include both cases, with the first robbed and with the first one save. And since every house is in a circle, it really doesn't matter where is the starting point if your algorithm is a correct one.

Then I turned to DFS. Since a lot of DP problem can be rewrote in a cached DFS(memorized DFS). It took me some time and finally I gave up this idea since I dont know what to cache.

The final result is easy. It is always like that. I realize I just need to change the initial condition and  run DP twice.

 public class Solution {  
   public int rob(int[] nums) {  
     return Math.max(circle_rob(nums, true), circle_rob(nums, false));  
   }  
     
   private int circle_rob(int[] nums, boolean robFirst){  
     // edge case  
     if(nums == null || nums.length == 0) return 0;  
       
     int[] opt = new int[nums.length+1];  
       
     // initial condition  
     opt[0] = 0;  
     opt[1] = robFirst?nums[0]:0;  
       
     // iteration  
     for(int i = 2;i < opt.length;i++){  
       if(i!=opt.length-1){   
         // normal case  
         opt[i] = Math.max(opt[i-2] + nums[i-1], opt[i-1]);  
       }else{  
         // last robbery  
         opt[i] = robFirst?opt[i-1]:Math.max(opt[i-2]+nums[i-1],opt[i-1]);  
       }  
     }  
       
     return opt[opt.length-1];  
   
   }  
     
     
 }  

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true 

Naive Thinking: Similar to Implement Trie(prefix-tree) . But pattern '.' was included. For addWord() method, '.' doesn't affect the process since its not necessary to combine '.ad' and 'bad'. It's okay to leave both in the tree. While for search() method, when '.' appear in the word, we need to search all child nodes. when '.' appear in the node, we need to search this node also. So I apply a DFS approach to do search().

 public class WordDictionary {  
     
   LetterNode head = new LetterNode('*');  
   
   // Adds a word into the data structure.  
   public void addWord(String word) {  
     LetterNode cur = head;  
     for(int i = 0;i < word.length();i++){  
       if(cur.next.containsKey(word.charAt(i))){  
         cur = cur.next.get(word.charAt(i));  
       }else{  
         LetterNode son = new LetterNode(word.charAt(i));  
         cur.next.put(word.charAt(i), son);  
         cur = son;  
       }  
     }  
     cur.isEnd = true;  
   }  
   
   // Returns if the word is in the data structure. A word could  
   // contain the dot character '.' to represent any one letter.  
   public boolean search(String word) {  
     // DFS  
     return search(head, word, 0);  
   }  
     
   private boolean search(LetterNode node, String word, int layer){  
     LetterNode son = null, dot = null;  
     // ending case  
     if(node == null) return false;  
     if(layer == word.length()) return node.isEnd;  
       
     // general case  
     if(word.charAt(layer)=='.'){   
       // Go though all next nodes when '.' appear  
       Iterator iter = node.next.entrySet().iterator();  
       while(iter.hasNext()){  
         Map.Entry pair = (Map.Entry)iter.next();  
         if(search((LetterNode)pair.getValue(), word, layer+1))  
           return true;  
       }  
     }else{  
       // Go though target character nodes and '.' nodes  
       if(node.next.containsKey(word.charAt(layer)))  
         son = node.next.get(word.charAt(layer));  
       if(node.next.containsKey('.'))  
         dot = node.next.get('.');  
       if(son!=null || dot!=null)  
         return search(son, word, layer+1) || search(dot, word, layer+1);  
     }  
         
     return false;  
   }  
     
   class LetterNode{  
     Map<Character, LetterNode> next;  
     char letter;  
     boolean isEnd;  
     LetterNode(char c){  
       this.letter = c;  
       this.next = new HashMap<Character, LetterNode>();  
       this.isEnd = false;  
     }  
   }  
 }  
   
 // Your WordDictionary object will be instantiated and called as such:  
 // WordDictionary wordDictionary = new WordDictionary();  
 // wordDictionary.addWord("word");  
 // wordDictionary.search("pattern");  

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].


Naive Thinking: Everything the same with Course Schedule I . Return the order of topological sort instead of whether can it be passed. Use an arraylist to store the order first. And then check if the size meets the number of courses. Then copy the arraylist to output array.

 public class Solution {  
   public int[] findOrder(int numCourses, int[][] prerequisites) {  
       
     // initilization  
     int[] rslt = new int[0];  
     List<Integer> order = new ArrayList<Integer>();  
     Queue<Integer> zero_pre_courses = new LinkedList<Integer>();  
     List<Course> courses = new ArrayList<Course>();  
     for(int i = 0;i < numCourses;i++) courses.add(new Course(i));  
       
     // read in prerequisite infomation  
     for(int i = 0;i < prerequisites.length;i++){  
       courses.get(prerequisites[i][0]).prerequisite.add(prerequisites[i][1]);  
       courses.get(prerequisites[i][1]).advanced.add(prerequisites[i][0]);  
     }  
       
     // group zero_prerequisite courses  
     for(int i = 0;i < numCourses;i++)  
       if(courses.get(i).prerequisite.isEmpty()) zero_pre_courses.add(i);  
       
     // topological sort  
     while(!zero_pre_courses.isEmpty()){  
       int curNum = zero_pre_courses.poll();  
       order.add(curNum);  
       Iterator<Integer> iter = courses.get(curNum).advanced.iterator();  
       while(iter.hasNext()){  
         int advNum = iter.next();  
         courses.get(advNum).prerequisite.remove(curNum);  
         if(courses.get(advNum).prerequisite.isEmpty()) zero_pre_courses.add(advNum);  
       }  
     }  
       
     // generate result  
     if(order.size() == numCourses){  
       rslt = new int[numCourses];  
       for(int i = 0;i < numCourses;i++)  
         rslt[i] = order.get(i);  
     }  
       
     return rslt;  
   }  
     
   class Course{  
     Set<Integer> prerequisite;  
     Set<Integer> advanced;  
     int label;  
     Course(int l){  
       this.label = l;  
       this.prerequisite = new HashSet<Integer>();  
       this.advanced = new HashSet<Integer>();  
     }  
   }  
 }  

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.

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

 class TrieNode {  
   // Initialize your data structure here.  
   public TrieNode() {  
       
   }  
 }  
   
 public class Trie {  
   private TrieNode root;  
   
   public Trie() {  
     root = new TrieNode();  
   }  
   
   // Inserts a word into the trie.  
   public void insert(String word) {  
       
   }  
   
   // Returns if the word is in the trie.  
   public boolean search(String word) {  
       
   }  
   
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   public boolean startsWith(String prefix) {  
       
   }  
 }  
   
 // Your Trie object will be instantiated and called as such:  
 // Trie trie = new Trie();  
 // trie.insert("somestring");  
 // trie.search("key");  

Naive Thinking: At first I didn't know Trie. Here is the definition from Wikipedia.  https://en.wikipedia.org/?title=Trie

The structure was given. Only need to fill in the methods. The structure tell me that each node is described as TrieNode. And the whole trie is just referred by its root. Thus, a TrieNode should contain children TrieNode attributes in order to have access to every TrieNode in the tree via root TrieNode.

The search() method and startwith() method differs in that the last character must be an ending TrieNode in search() while startwith() doesn't have to be.

Below is my implementation. I use HashMap to maintain children TrieNode relationship.

 class TrieNode {  
   // Initialize your data structure here.  
   public String data;  
   public Map<Character, TrieNode> children;  
   public boolean isEnd;  
   public TrieNode() {  
     data = new String();  
     children = new HashMap<Character, TrieNode>();  
     isEnd = false;  
   }  
     
   public TrieNode(String s){  
     data = s;  
     children = new HashMap<Character, TrieNode>();  
     isEnd = false;  
   }  
 }  
   
 public class Trie {  
   private TrieNode root;  
   
   public Trie() {  
     root = new TrieNode();  
   }  
   
   // Inserts a word into the trie.  
   public void insert(String word) {  
     TrieNode cur = root;  
     for(int i = 0;i < word.length();i++){  
       if(cur.children.containsKey(word.charAt(i))){  
         cur = cur.children.get(word.charAt(i));  
       }else{  
         String s = root.data + word.charAt(i);  
         TrieNode child = new TrieNode(s);  
         cur.children.put(word.charAt(i), child);  
         cur = child;  
       }  
     }  
     cur.isEnd = true;  
   }  
   
   // Returns if the word is in the trie.  
   public boolean search(String word) {  
     TrieNode cur = root;  
     for(int i = 0;i < word.length();i++){  
       if(cur.children.containsKey(word.charAt(i)))  
         cur = cur.children.get(word.charAt(i));  
       else  
         return false;  
     }  
     return cur.isEnd;  
   }  
   
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   public boolean startsWith(String prefix) {  
     TrieNode cur = root;  
     for(int i = 0;i < prefix.length();i++){  
       if(cur.children.containsKey(prefix.charAt(i)))  
         cur = cur.children.get(prefix.charAt(i));  
       else  
         return false;  
     }  
     return true;  
   }  
 }  
   
   

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Naive Thinking: The description leads to a topological sort solution. But to execute a topological sort is not easy. If I directly use the 2D array on each iteration, I need to go though all 2D vectors. That's definitely not a good run time. The input 2D array needs to be preprocessed before implementing topological sort on it. After several trial, I find out that use a extra Course object with both prerequisite and advanced course attributes sounds.

 public class Solution {  
   public boolean canFinish(int numCourses, int[][] prerequisites) {  
     boolean exit = true;  
     List<Course> courses = new ArrayList<Course>();  
     Queue<Course> zero_pre_courses = new LinkedList<Course>();  
       
     // initialize courses list  
     for(int i = 0;i < numCourses;i++) courses.add(new Course(i));  
       
     // read in course prerequisite relationship  
     for(int i = 0;i < prerequisites.length;i++){  
       courses.get(prerequisites[i][0]).advanced.add(prerequisites[i][1]);  
       courses.get(prerequisites[i][1]).prerequisite.add(prerequisites[i][0]);  
     }  
       
     // group all zero prerequisite courses  
     for(int i = 0;i < numCourses;i++)  
       if(courses.get(i).prerequisite.isEmpty()) zero_pre_courses.add(courses.get(i));  
       
     // topological sort  
     while(!zero_pre_courses.isEmpty()){  
       Course course = zero_pre_courses.poll();  
       Iterator<Integer> iter = course.advanced.iterator();  
       while(iter.hasNext()){  
         int advancedCourseLabel = (int)iter.next();  
         Course advancedCourse = courses.get(advancedCourseLabel);  
         advancedCourse.prerequisite.remove(course.label);  
         if(advancedCourse.prerequisite.isEmpty()) zero_pre_courses.add(advancedCourse);  
       }  
       course.label = -1; // set label to -1 as the course is took  
     }  
       
     // check if all courses are took  
     for(int i = 0;i < numCourses;i++)  
       if(courses.get(i).label!=-1) exit = false;  
       
     return exit;  
       
   }  
   class Course{  
     Set<Integer> prerequisite;  
     Set<Integer> advanced;  
     int label;  
     Course(int l){  
       label = l;  
       prerequisite = new HashSet<Integer>();  
       advanced = new HashSet<Integer>();  
     }  
   }  
 }  

Reverse Linked List

Reverse a singly linked list.

Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?

Naive Thinking: At first, I thought it cannot be done in O(1) space, so I use a stack and go through the linked-list once pushing one by one into stack. And then pop from the stack one by one. Not surprisingly, I got memory limit exceed. That's probably a sign that I used extra space. So I begin to think about using O(1) space. Just pointing each Node's next pointer to its previous one. In such a process, I need to always note down its next Node first or I will lost the remaining Nodes.

Iteratively:

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   // iteratively  
   public ListNode reverseList(ListNode head) {  
     ListNode pre = null, cur = head, next = null;  
     while(cur!=null){  
       next = cur.next;  
       cur.next = pre;  
       pre = cur;  
       cur = next;  
     }  
     return pre;  
   }  
 }  

Recursively:

 public class Solution {  
   // recursively  
   public ListNode reverseList(ListNode head) {  
     return reverseList(null, head);  
   }  
   private ListNode reverseList(ListNode pre, ListNode cur){  
     // ending case  
     if(cur==null) return pre;  
     // general case  
     ListNode next = cur.next;  
     cur.next = pre;  
     return reverseList(cur, next);  
   }  
 }  

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Naive Way: Use a HashMap to note down the mapping. Also use .containsKey and .containsValue function to check duplicates. The point being easily ignored is the value also needs to be uniquely mapped. No two characters can map to the same value.

 public class Solution {  
   public boolean isIsomorphic(String s, String t) {  
     Map<Character, Character> map = new HashMap<Character, Character>();  
     for(int i = 0;i < s.length();i++){  
       if(map.containsKey(s.charAt(i))){  
         if(t.charAt(i)!=map.get(s.charAt(i))) return false;  
       }else{  
         if(map.containsValue(t.charAt(i))) return false;  
         map.put(s.charAt(i), t.charAt(i));  
       }  
     }  
     return true;  
   }  
 }  

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5


Naive Way: It is the most common way of manipulating linked list. But as for linked list, null pointer will always be a problem.

As usual, I use a fake head pointer to make my code more smooth.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public ListNode removeElements(ListNode head, int val) {  
     ListNode fake = new ListNode(0);  
     ListNode pre = fake;  
     fake.next = head;  
     while(pre.next!=null){  
       ListNode cur = pre.next;  
       if(cur.val==val)  
         pre.next = cur.next; // remove the node  
       else  
         pre = cur;  
     }  
     return fake.next;  
   }  
 }  

Happy Number

Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number

• 1² + 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

Naive Way: The statement is describing a recursive process. So it is obvious that the question want me to write a recursive method. The logic has been stated and clear. Base case (ending condition) is either n=1 or n has been visited. And since I need to mark whether a number has been visited, a hashset is required.

 public class Solution {  
   Set<Integer> visited = new HashSet<Integer>();  
   public boolean isHappy(int n) {  
     // base case  
     if(n==1) return true;  
     // visited  
     if(visited.contains(n)) return false;  
     // main processing  
     int sum = 0;  
     visited.add(n);  
     while(n!=0){  
       int lastDigit = n % 10;  
       sum += lastDigit * lastDigit;  
       n /= 10;  
     }  
     return isHappy(sum);  
   }  
 }  

Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.

Naive Way: My first thought was to use "&" operation going though all numbers between m and n inclusively. That gets a TLE. I later wrote some test cases and find out that "&" operation is hard to keep even one bit when there is a gap between n and m.
For example: 4-8: 0100, 0101, 0110, 0111, 1000. result is 0000.
It turns out that m and n need to have same highest bit, otherwise the result will be 0.

I tried many times and finally find out that a method use only bit shift operation will do the trick. Any ">" or "<" compare condition will possibly ruin he algorithm because 0x80000000 is a negative number.

My method is a recursive one. The idea is keep finding highest bit of m, check if n has a higher bit. And let the recursive call do the rest bits.

 public class Solution {  
   public int rangeBitwiseAnd(int m, int n) {  
     return rangeBitwiseAnd(m,n,0x80000000);  
   }  
     
   private int rangeBitwiseAnd(int m, int n, int shift){  
       
     // edge case  
     if(m==0) return 0;  
       
     // find highest bit of m  
     while((shift & m) == 0){  
       if((shift & n) != 0) return 0;  
       shift >>>= 1;  
     }  
       
     return shift + rangeBitwiseAnd(m - shift, n - shift, shift);  
   }  
 }  

Improved Way: After viewing the Discuss, I find there are tons of lot better solutions.

One is from applewolf, who find out that keep comparing from lower bits to higher bits can do the trick.

 int rangeBitwiseAnd(int m, int n) {  
   return (n > m) ? (rangeBitwiseAnd(m/2, n/2) << 1) : m;  
 }  

Another is from haw64, who find out that the result of AND operation is just left most consecutive common part of n and m (just two numbers, no need of numbers in between).

 public int rangeBitwiseAnd(int m, int n) {  
     int count = 0;  
     while(m != n){  
       m >>= 1;  
       n >>= 1;  
       count++;  
     }  
     return m<<=count;  
   }  

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:

11110
11010
11000
00000

Answer: 1
Example 2:

11000
11000
00100
00011

Answer: 3

Naive Way: Use DFS to go though all grid cells. Use a hashset to keep visited grid cells. Run time is O(n^2). And space is O(n^2).

 public class Solution {  
   public int numIslands(char[][] grid) {  
     Set<List<Integer>> visited = new HashSet<List<Integer>>();  
     int num = 0;  
     for(int i = 0;i < grid.length;i++)  
       for(int j = 0;j < grid[0].length;j++)  
         num+=dfs(grid,i,j,visited);  
     return num;  
   }  
   private int dfs(char[][] grid, int x, int y, Set<List<Integer>> visited){  
     // edge case  
     if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) return 0;  
     // island  
     if(grid[x][y] == '1'){  
       List<Integer> list = new ArrayList<Integer>();  
       list.add(x);  
       list.add(y);  
       if(!visited.contains(list)){  
         visited.add(list);  
         dfs(grid, x-1, y, visited);  
         dfs(grid, x+1, y, visited);  
         dfs(grid, x, y-1, visited);  
         dfs(grid, x, y+1, visited);  
         return 1;  
       }  
     }  
     return 0;  
   }  
 }  

I saw a algorithm in Discuss use the original grid to store visited grid cells. Thus reduce space used to O(1).

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].


Naive Way: Use a level-order traversal and always note down the last TreeNode value in the result.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public List<Integer> rightSideView(TreeNode root) {  
     List<Integer> list = new ArrayList<Integer>();  
     List<TreeNode> cur_layer = new ArrayList<TreeNode>();  
     // edge case  
     if(root==null) return list;  
     // initialize current layer  
     cur_layer.add(root);  
     // level-order traversal  
     while(!cur_layer.isEmpty()){  
       list.add(cur_layer.get(cur_layer.size()-1).val);  
       List<TreeNode> next_layer = new ArrayList<TreeNode>();  
       for(TreeNode node: cur_layer){  
         if(node.left!=null) next_layer.add(node.left);  
         if(node.right!=null) next_layer.add(node.right);  
       }  
       cur_layer = next_layer;  
     }  
     return list;  
   }  
 }  

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Naive Thinking: First thought was to use DP. The logic is as follows:
opt[i] // the maximum amount of money one rob without alerting the police.
// base case
opt[0] = 0
opt[1] = num[0]
// iteration
opt[i] = max(opt[i-1], opt[i-2]+num[i-1])

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     int opt[] = new int[num.length+1];  
     // base case  
     opt[0] = 0;  
     opt[1] = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++)  
       opt[i] = Math.max(opt[i-1], opt[i-2] + num[i-1]);  
     return opt[num.length];  
   }  
 }  

From the structure of the code. It is easy to see the O(N) space could be constrained to O(1).

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     // base case  
     int pre = 0;  
     int cur = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++){  
       int temp = cur;  
       cur = Math.max(cur, pre + num[i-1]);  
       pre = temp;  
     }  
     return cur;  
   }  
 }  

Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.


Naive Way: First came up with a DFS method. Need a hashset for each path to store visited positions.

 public class Solution {  
   class Node{  
     int x,y;  
     Node(int x, int y){  
       this.x = x;  
       this.y = y;  
     }  
     @Override  
     public boolean equals(Object other){  
       if (!(other instanceof Node))  
         return false;  
       Node n = (Node)other;  
       return this.x==n.x && this.y==n.y;  
     }  
     @Override  
     public int hashCode(){  
       return x << 16 | y;  
     }  
   }  
   public boolean exist(char[][] board, String word) {  
     for(int i = 0;i < board.length;i++)  
       for(int j = 0;j < board[i].length;j++){  
           Node node = new Node(i,j);  
           Stack<Node> stack = new Stack<Node>();  
           Set<Node> set = new HashSet<Node>();  
           stack.add(node);  
           set.add(node);  
           if(dfs(board, node, word, 0, stack, set))  
             return true;  
         }  
     return false;  
   }  
   private boolean dfs(char[][] board, Node node, String word, int index, Stack<Node> stack, Set<Node> set){  
     /* ending cases */  
     // find a path  
     if(index == word.length()) return true;  
     // invalid node  
     if(node.x < 0 || node.x >= board.length || node.y < 0 || node.y >= board[0].length) return false;  
     // not match  
     if(board[node.x][node.y] != word.charAt(index)) return false;  
     // recusive case  
     Node up = new Node(node.x-1, node.y);  
     if(!set.contains(up)){  
       stack.push(up);  
       set.add(up);  
       if(dfs(board, up, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(up);  
     }  
     Node down = new Node(node.x+1, node.y);  
     if(!set.contains(down)){  
       stack.push(down);  
       set.add(down);  
       if(dfs(board, down, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(down);  
     }  
     Node left = new Node(node.x, node.y-1);  
     if(!set.contains(left)){  
       stack.push(left);  
       set.add(left);  
       if(dfs(board, left, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(left);  
     }  
     Node right = new Node(node.x, node.y+1);  
     if(!set.contains(right)){  
       stack.push(right);  
       set.add(right);  
       if(dfs(board, right, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(right);  
     }  
     return false;  
   }  
 }  

And then, I think I am bring too much extra stuff to a simple problem. Better use a 2D array to record used cell.

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     // edge case  
     if(board == null || board.length == 0) return false;  
     if(word.length() > board.length*board[0].length) return false;  
     boolean[][] used = new boolean[board.length][board[0].length];  
     for(int i = 0;i < board.length;i++){  
       for(int j = 0;j < board[0].length;j++){  
         used[i][j] = true;  
         if(dfs(board, i, j, word, 0, used)) return true;  
         used[i][j] = false;  
       }  
     }  
     return false;  
   }  
   private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){  
     // ending case  
     if(index==word.length()) return true;  
     if(board[x][y]!=word.charAt(index)) return false;  
     // recursive call  
     if(x-1 >= 0 && !used[x-1][y]){  
       used[x-1][y] = true;  
       if(dfs(board,x-1,y,word,index+1,used)) return true;  
       used[x-1][y] = false;  
     }  
     if(x+1 < board.length && !used[x+1][y]){  
       used[x+1][y] = true;  
       if(dfs(board,x+1,y,word,index+1,used)) return true;  
       used[x+1][y] = false;  
     }  
     if(y-1 >= 0 && !used[x][y-1]){  
       used[x][y-1] = true;  
       if(dfs(board,x,y-1,word,index+1,used)) return true;  
       used[x][y-1] = false;  
     }  
     if(y+1 < board[0].length && !used[x][y+1]){  
       used[x][y+1] = true;  
       if(dfs(board,x,y+1,word,index+1,used)) return true;  
       used[x][y+1] = false;  
     }  
     return false;  
   }  
 }  

but this code get TLE for the longest "aaa.."" string case. And then I saw others' code and found a modified, much more elegant way.

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     // edge case  
     if(word == null || board == null || board.length == 0) return false;  
     if(word.length() > board.length*board[0].length) return false;  
     boolean[][] used = new boolean[board.length][board[0].length];  
     for(int i = 0;i < board.length;i++)  
       for(int j = 0;j < board[0].length;j++)  
         if(dfs(board, i, j, word, 0, used)) return true;  
     return false;  
   }  
   private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){  
     // ending case  
     if(index==word.length()) return true;  
     if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;  
     if(used[x][y] || board[x][y]!=word.charAt(index)) return false;  
     // recursive call  
     used[x][y] = true;  
     if(dfs(board,x-1,y,word,index+1,used)) return true;  
     if(dfs(board,x+1,y,word,index+1,used)) return true;  
     if(dfs(board,x,y-1,word,index+1,used)) return true;  
     if(dfs(board,x,y+1,word,index+1,used)) return true;  
     used[x][y] = false;  
     return false;  
   }  
 }  

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
] 

Naive Way: A recursive method is straightforward. Need to convey current index, n, current k as parameter to recursive function. It is a DFS idea.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     dfs(new Stack<Integer>(), 1, n, k, rslt);  
     return rslt;  
   }  
   private void dfs(Stack<Integer> path, int index, int n, int k, List<List<Integer>> rslt){  
     // ending case  
     if(k==0){  
       List<Integer> list = new ArrayList<Integer>(path);  
       rslt.add(list);  
       return;  
     }  
     // recursion case  
     for(int i = index;i <= n;i++){  
       path.push(i);  
       dfs(path, i+1, n, k-1, rslt);  
       path.pop();  
     }  
   }  
 }  

An iterative method correspondingly.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Deque<List<Integer>> gross = new ArrayDeque<List<Integer>>();  
     // edge case   
     if(k==0) return rslt;  
     // initialize the rslt  
     for(int i = 1;i <= n-k+1;i++){  
       List<Integer> list = new ArrayList<Integer>();  
       list.add(i);  
       gross.offerLast(list);  
     }  
     // iteration on k  
     int ind = 1;  
     while(ind++ < k){  
       int length = gross.size();  
       for(int i = 0;i < length;i++){  
         List<Integer> list = gross.pollFirst();  
         int num = list.get(list.size()-1);  
         for(int j = num+1;j <= n;j++){  
           List<Integer> new_list = new ArrayList<Integer>(list);  
           new_list.add(j);  
           gross.offerLast(new_list);  
         }  
       }  
     }  
     // add to result  
     while(!gross.isEmpty()) rslt.add(gross.pollFirst());  
     return rslt;  
   }  
 }  

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