Single Number II : How to come up with Bit Manipulation Formula

Problem Description

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear running time complexity. Could you implement it without using extra memory?

Solutions
By following up Single Number problem we can solve this problem by using Hash Table. So we will not discuss that solution here.
At first, in order to solve the problem, we try to make it simpler. We only consider the right most bit of each number, and count the number of bits that equals to 1. Call "mars" is the number of 1 bits. We also call "elon" is the number that appear only once, and "elonBit" is the rightmost bit of "elon" (The terms are just for fun because Elon Musk is my idol :)).

Our observation is that if "mars" is a multiple of 3 then "elonBit" must be 0,  otherwise it is 1. We can repeat this procedure for all other bits. This is what we have in the following code.

I. Counting the number of bit 1.

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.           
4.         int result = 0;  
5.         for(int i = 0; i<32; i++){  
6.             int elonBit = 1 << i;  
7.             int mars = 0;  
8.             for(int j=0; j<nums.length; j++){  
9.                 if((nums[j] & elonBit) != 0) // if it is bit 1  
10.                     mars++;  
11.             }  
12.             if (mars % 3 == 1) result |= elonBit;  
13.         }  
14.         return result;  
15.     }  
16. }  

public class Solution {
    public int singleNumber(int[] nums) {
        
        int result = 0;
        for(int i = 0; i<32; i++){
            int elonBit = 1 << i;
            int mars = 0;
            for(int j=0; j<nums.length; j++){
                if((nums[j] & elonBit) != 0) // if it is bit 1
                    mars++;
            }
            if (mars % 3 == 1) result |= elonBit;
        }
        return result;
    }
}

However, we see that the actual value of "mars" is not really important. Every time "mars" equal to 3, we can reset "mars" to 0. Since we are working with bits, we can represent "mars" by 2 bits p and q.

Since with 2 bits, we can represent 4 numbers, so we have different ways to represent the states from 0 to 2 (3 states). We will pick the natural way: 00 for state 0, 01 for state 1, and 10 for 2 (NOTE: if we choose another way to represent, we may come up with different solution later, so you should try it ^_^). With this way of representing, we see that when mars % 3 = 0, pq = 00, and when mars % 3 = 1, pq = 01. Therefore, the final value of q will be exactly the value of "elonBit".

Now we call r is the corresponding bit of a number in the array. If r = 1, we have the following transitions: (00 + 1 = 01), (01 + 1 = 10), (10 + 1 = 00). (The + means the transition with condition that we met bit 1).

We have the following transition table, where (old_p, old_q) represents the state before we examine a number, and (p, q) represents the state after that.
_____________________________
|old_p |old_q |   r    |    p      | q        |
--------------------------------------------
|   0     |   0     |   0    |    0     | 0         |
--------------------------------------------
|   0     |   1     |   0    |    0     | 1         |
--------------------------------------------
|   1     |   0     |   0    |    1     | 0         |
--------------------------------------------
|   0     |   0     |   1    |    0     | 1         |
--------------------------------------------
|   0     |   1     |   1    |    1     | 0         |
--------------------------------------------
|   1     |   0     |   1    |    0     | 0         |
--------------------------------------------

Based on the above transition table, we can derive the formula of p and q based on old_p, old_q, and r.
p = (old_p & ~old_q & ~r) | (~old_p & old_q & r)
q = (~old_p & old_q& ~r) | (~old_p & ~old_q & r)

Based on this, we jump directly to coding and have the following code.
II. Method 2

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.           
4.        int p = 0;  
5.        int q = 0;  
6.          
7.        int old_p, old_q, r;  
8.        for(int i = 0; i<nums.length; i++){  
9.            old_p = p; old_q = q;  
10.            r = nums[i]; //this to make it consistent with our analysis.  
11.            p = (old_p & ~old_q & ~r) | (~old_p & old_q & r);  
12.            q = (~old_p & old_q& ~r) | (~old_p & ~old_q & r);  
13.        }  
14.        return q;  
15.     }  
16. }  

public class Solution {
    public int singleNumber(int[] nums) {
        
       int p = 0;
       int q = 0;
       
       int old_p, old_q, r;
       for(int i = 0; i<nums.length; i++){
           old_p = p; old_q = q;
           r = nums[i]; //this to make it consistent with our analysis.
           p = (old_p & ~old_q & ~r) | (~old_p & old_q & r);
           q = (~old_p & old_q& ~r) | (~old_p & ~old_q & r);
       }
       return q;
    }
}

Now, we see that in this assignment:
p = (old_p & ~old_q & ~r) | (~old_p & old_q & r)
we have old_q = q, and old_p is p before that assignment.
So the formula become:
p = (p & ~q& ~r) | (~p& q& r)

As a consequence, we have the code:
III. Method 3: Improvement on Method 2

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.        int p = 0;  
4.        int q = 0;  
5.        int r, old_p;  
6.        for(int i = 0; i<nums.length; i++){  
7.           r = nums[i]; //this to make it consistent with our analysis.   
8.           old_p = p;  
9.           p = (p & ~q& ~r) | (~p& q& r);  
10.           q = (~old_p & q& ~r) | (~old_p & ~q & r);  
11.        }  
12.        return q;  
13.     }  
14. }  

public class Solution {
    public int singleNumber(int[] nums) {
       int p = 0;
       int q = 0;
       int r, old_p;
       for(int i = 0; i<nums.length; i++){
          r = nums[i]; //this to make it consistent with our analysis. 
          old_p = p;
          p = (p & ~q& ~r) | (~p& q& r);
          q = (~old_p & q& ~r) | (~old_p & ~q & r);
       }
       return q;
    }
}

In the above code, it is still ugly because we need to use old_p. Why we cannot use p to replace old_p? Let's look at the triple (old_q, r, p) in the transition table. Its values include (0, 0, 0), (1, 0, 0), (0, 0, 1), (0, 1, 0), (1, 1, 1), (0, 1, 0). The triple (0, 1, 0) is duplicated, therefore information is lost for this case.
We can try different transition tables!
|old_p |old_q |   r    |    p      | q        |
--------------------------------------------
|   0     |   0     |   0    |    0     | 0         |
--------------------------------------------
|   0     |   1     |   0    |    0     | 1         |
--------------------------------------------
|   1     |   1     |   0    |    1     | 1         |
--------------------------------------------
|   0     |   0     |   1    |    0     | 1         |
--------------------------------------------
|   0     |   1     |   1    |    1     | 1         |
--------------------------------------------
|   1     |   1     |   1    |    0     | 0         |
--------------------------------------------
It is pretty beautiful that in this table the triple (old_q, r, p) is unique, so we can use p to calculate q. And we are still able to use q to represents "elonBit" because for state 1, (p,q) = (0, 1)
p = (p & q & ~ r) | (~p & q & r)
q = (q & ~r & ~p) | (q & ~r & p) | (~q & r & ~p) | (q & r & p)
After reducing the above equations, we have:
p = q & (p ^ r)
q = p | (q ^ r)
IV. Method 4

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.        int p = 0;  
4.        int q = 0;  
5.        int r;  
6.        for(int i = 0; i<nums.length; i++){  
7.           r = nums[i]; //this to make it consistent with our analysis.   
8.           p = q & (p ^ r);  
9.           q = p | (q ^ r);  
10.        }  
11.        return q;  
12.     }  
13. }  

public class Solution {
    public int singleNumber(int[] nums) {
       int p = 0;
       int q = 0;
       int r;
       for(int i = 0; i<nums.length; i++){
          r = nums[i]; //this to make it consistent with our analysis. 
          p = q & (p ^ r);
          q = p | (q ^ r);
       }
       return q;
    }
}

After understanding all of this process, we can solve different problems. For example, given an array in which all elements appear 3 times but one element is missing. For example [0,0,0, 1,1, 2, 2, 2, 3, 3, 3] where one "1" is missing.
Since the state 2 is represented as (1,1), hence instead of "return q", we can simply return "p&q" in the above code.

Single Number

Problem Description

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solutions
I. Using Hash Table
We can solve this problem by simply counting the number of times a number appeared.
Java Code

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.         Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();  
4.         for(int i = 0; i<nums.length; i++){  
5.               
6.             if(!map.containsKey(nums[i])){  
7.                 map.put(nums[i], false);  
8.             }else{  
9.                 map.put(nums[i], true);  
10.             }  
11.         }  
12.         for(int i: map.keySet()){  
13.             if (!map.get(i)) return i;  
14.         }  
15.         return 0;  
16.     }  
17. }  

public class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for(int i = 0; i<nums.length; i++){
            
            if(!map.containsKey(nums[i])){
                map.put(nums[i], false);
            }else{
                map.put(nums[i], true);
            }
        }
        for(int i: map.keySet()){
            if (!map.get(i)) return i;
        }
        return 0;
    }
}

II. Bit manipulation
In this solution, we have the following observation, given an integer N:
0 ^ N = N
N ^ N = 0
Where ^ is the XOR operator.

view plainprint?

1. public class Solution {  
2.     public int singleNumber(int[] nums) {  
3.         int result = 0;  
4.         for (int i = 0; i<nums.length; i++){  
5.               
6.             result ^= nums[i];  
7.         }  
8.         return result;  
9.     }  
10. }  

public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i<nums.length; i++){
            
            result ^= nums[i];
        }
        return result;
    }
}

House Robber II

Problem Description

Note: This is an extension of House Robber.

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.

PS: In real life, we should not think of robbery (^_^) as if we were thieves. We can think of this as a precaution to design the actual alarm system better!

Solution

I. Extend the previous solution
In the previous example, we can "rob" from the first house to the last house. In this example, we cannot "rob" the first and last house at the same time. So we can think simply that we can choose to "rob" from the second house to the last house, or "rob" from the first house to the second-last house.

Figure 1: Choose range of houses to "rob"!

view plainprint?

1. class Solution(object):  
2.     def rob(self, nums):  
3.         """ 
4.         :type nums: List[int] 
5.         :rtype: int 
6.         """  
7.         n = len(nums)  
8.         if n == 0: return 0  
9.         if n < 4: return max(nums)  
10.   
11.         first, second = 0, 0  
12.         for i in nums[:-1]: first, second = second, max(first + i, second)  
13.         result = second  
14.   
15.         first, second = 0, 0  
16.         for i in nums[1:]: first, second = second, max(first + i, second)  
17.         return max(result, second)  

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0: return 0
        if n < 4: return max(nums)

        first, second = 0, 0
        for i in nums[:-1]: first, second = second, max(first + i, second)
        result = second

        first, second = 0, 0
        for i in nums[1:]: first, second = second, max(first + i, second)
        return max(result, second)

Number of 1 Bits

Problem Description
Calculate Hamming Weight of an unsigned integer.
NOTE: Hamming Weight of an unsigned integer is the number of 1 bits in its unsigned representation.
Solution
In order to solve the problem, we iteratively check the right most bit if it is 1, then shift all the bits to the right 1 bit (i.e divide it by 2). The code for this implementation is in part I (java) & part II (C++).

We can also do a trick here. It's good to know that we can drop the rightmost set bit by the operation (n&(n-1)).

It is in part III & IV. In part V, we see different naive implementations.
I. Java

view plainprint?

1. public class Solution {  
2.     // you need to treat n as an unsigned value  
3.     public int hammingWeight(int n) {  
4.         int count = 0;  
5.           
6.         while(n != 0){  
7.             if((n & 1) == 1) count++;  
8.             n >>>= 1;  
9.         }  
10.         return count;  
11.     }  
12. }  

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

II. C++

view plainprint?

1. class Solution {  
2. public:  
3.     int hammingWeight(uint32_t n) {  
4.         int count = 0;  
5.         while(n != 0){  
6.             if(n & 1) count++;  
7.             n >>=1;  
8.         }  
9.         return count;  
10.     }  
11. };  

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n != 0){
            if(n & 1) count++;
            n >>=1;
        }
        return count;
    }
};

III. Java with (n & (n-1)) Solution

view plainprint?

1. public class Solution {  
2.     // you need to treat n as an unsigned value  
3.     public int hammingWeight(int n) {  
4.         int count = 0;  
5.         while(n!=0){  
6.             n &= (n-1);  
7.             count++;  
8.         }  
9.         return count;  
10.     }  
11. }  

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

IV. C++ with (n & (n-1)) Solution

view plainprint?

1. class Solution {  
2. public:  
3.     int hammingWeight(uint32_t n) {  
4.         int count = 0;  
5.       
6.         while (n) {  
7.             n &= (n - 1);  
8.             count++;  
9.         }  
10.       
11.         return count;  
12.     }  
13. };  

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
    
        while (n) {
            n &= (n - 1);
            count++;
        }
    
        return count;
    }
};

V. Naive Java Solutions (From Wiki: Hamming Weight with modification)

view plainprint?

1. public class Solution {  
2.       
3.     public int hammingWeight(int n) {  
4.         return popcount_3(n);     
5.     }  
6.     // you need to treat n as an unsigned value  
7.     final int m1  = 0x55555555; //binary: 0101...  
8.     final int m2  = 0x33333333; //binary: 00110011..  
9.     final int m4  = 0x0f0f0f0f; //binary:  4 zeros,  4 ones ...  
10.     final int m8  = 0x00ff00ff; //binary:  8 zeros,  8 ones ...  
11.     final int m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ...  
12.     final int hff = 0xffffffff; //binary: all ones  
13.     final int h01 = 0x01010101; //the sum of 256 to the power of 0,1,2,3...  
14.       
15.     //This is a naive implementation, shown for comparison,  
16.     //and to help in understanding the better functions.  
17.     //It uses 24 arithmetic operations (shift, add, and).  
18.     int popcount_1(int x) {  
19.         x = (x & m1 ) + ((x >>>  1) & m1 ); //put count of each  2 bits into those  2 bits   
20.         x = (x & m2 ) + ((x >>>  2) & m2 ); //put count of each  4 bits into those  4 bits   
21.         x = (x & m4 ) + ((x >>>  4) & m4 ); //put count of each  8 bits into those  8 bits   
22.         x = (x & m8 ) + ((x >>>  8) & m8 ); //put count of each 16 bits into those 16 bits   
23.         x = (x & m16) + ((x >>> 16) & m16); //put count of each 32 bits into those 32 bits   
24.         return x;  
25.     }  
26.       
27.     //This uses fewer arithmetic operations than any other known    
28.     //implementation on machines with slow multiplication.  
29.     //It uses 17 arithmetic operations.  
30.     int popcount_2(int x) {  
31.         x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits  
32.         x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits   
33.         x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits   
34.         x += x >>>  8;  //put count of each 16 bits into their lowest 8 bits  
35.         x += x >>> 16;  //put count of each 32 bits into their lowest 8 bits  
36.         return x & 0x7f;  
37.     }  
38.       
39.     //This uses fewer arithmetic operations than any other known    
40.     //implementation on machines with fast multiplication.  
41.     //It uses 12 arithmetic operations, one of which is a multiply.  
42.     int popcount_3(int x) {  
43.         x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits  
44.         x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits   
45.         x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits   
46.         return (x * h01)>>>24;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...   
47.     }  
48. }  

public class Solution {
    
    public int hammingWeight(int n) {
        return popcount_3(n);   
    }
    // you need to treat n as an unsigned value
    final int m1  = 0x55555555; //binary: 0101...
    final int m2  = 0x33333333; //binary: 00110011..
    final int m4  = 0x0f0f0f0f; //binary:  4 zeros,  4 ones ...
    final int m8  = 0x00ff00ff; //binary:  8 zeros,  8 ones ...
    final int m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ...
    final int hff = 0xffffffff; //binary: all ones
    final int h01 = 0x01010101; //the sum of 256 to the power of 0,1,2,3...
    
    //This is a naive implementation, shown for comparison,
    //and to help in understanding the better functions.
    //It uses 24 arithmetic operations (shift, add, and).
    int popcount_1(int x) {
        x = (x & m1 ) + ((x >>>  1) & m1 ); //put count of each  2 bits into those  2 bits 
        x = (x & m2 ) + ((x >>>  2) & m2 ); //put count of each  4 bits into those  4 bits 
        x = (x & m4 ) + ((x >>>  4) & m4 ); //put count of each  8 bits into those  8 bits 
        x = (x & m8 ) + ((x >>>  8) & m8 ); //put count of each 16 bits into those 16 bits 
        x = (x & m16) + ((x >>> 16) & m16); //put count of each 32 bits into those 32 bits 
        return x;
    }
    
    //This uses fewer arithmetic operations than any other known  
    //implementation on machines with slow multiplication.
    //It uses 17 arithmetic operations.
    int popcount_2(int x) {
        x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits
        x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits 
        x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits 
        x += x >>>  8;  //put count of each 16 bits into their lowest 8 bits
        x += x >>> 16;  //put count of each 32 bits into their lowest 8 bits
        return x & 0x7f;
    }
    
    //This uses fewer arithmetic operations than any other known  
    //implementation on machines with fast multiplication.
    //It uses 12 arithmetic operations, one of which is a multiply.
    int popcount_3(int x) {
        x -= (x >>> 1) & m1;             //put count of each 2 bits into those 2 bits
        x = (x & m2) + ((x >>> 2) & m2); //put count of each 4 bits into those 4 bits 
        x = (x + (x >>> 4)) & m4;        //put count of each 8 bits into those 8 bits 
        return (x * h01)>>>24;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
    }
}

Binary Tree Paths

Problem Description

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Solution
I. Java Solution

view plainprint?

1. /** 
2.  * Definition for a binary tree node. 
3.  * public class TreeNode { 
4.  *     int val; 
5.  *     TreeNode left; 
6.  *     TreeNode right; 
7.  *     TreeNode(int x) { val = x; } 
8.  * } 
9.  */  
10. public class Solution {  
11.     public List<String> binaryTreePaths(TreeNode root) {  
12.         List<String> result = new ArrayList<String>();  
13.           
14.         if(root == null) return result;  
15.         LinkedList<TreeNode> path = new LinkedList<TreeNode>();  
16.           
17.         path.push(root);  
18.           
19.         TreeNode temp;  
20.         while(!path.isEmpty()){  
21.             temp = path.peek();  
22.             if(temp.left != null){  
23.                 path.push(temp.left);  
24.             }else if(temp.right != null){  
25.                 path.push(temp.right);  
26.             }else{  
27.                 result.add(listToString(path));  
28.                 temp = path.pop();  
29.                 while(!path.isEmpty()){  
30.                     if(path.peek().left == temp  
31.                         && path.peek().right!=null){  
32.                         path.push(path.peek().right);  
33.                         break;  
34.                     }  
35.                     temp = path.pop();  
36.                 }  
37.             }  
38.               
39.         }  
40.       
41.         return result;  
42.     }  
43.       
44.     public String listToString(LinkedList<TreeNode> path){  
45.         ListIterator<TreeNode> iterator = path.listIterator(path.size());  
46.         StringBuilder builder = new StringBuilder();  
47.         builder.append(iterator.previous().val);  
48.         while(iterator.hasPrevious()){  
49.             builder.append("->" + iterator.previous().val);  
50.         }  
51.         return builder.toString();  
52.     }  
53. }  

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<String>();
        
        if(root == null) return result;
        LinkedList<TreeNode> path = new LinkedList<TreeNode>();
        
        path.push(root);
        
        TreeNode temp;
        while(!path.isEmpty()){
            temp = path.peek();
            if(temp.left != null){
                path.push(temp.left);
            }else if(temp.right != null){
                path.push(temp.right);
            }else{
                result.add(listToString(path));
                temp = path.pop();
                while(!path.isEmpty()){
                    if(path.peek().left == temp
                        && path.peek().right!=null){
                        path.push(path.peek().right);
                        break;
                    }
                    temp = path.pop();
                }
            }
            
        }
    
        return result;
    }
    
    public String listToString(LinkedList<TreeNode> path){
        ListIterator<TreeNode> iterator = path.listIterator(path.size());
        StringBuilder builder = new StringBuilder();
        builder.append(iterator.previous().val);
        while(iterator.hasPrevious()){
            builder.append("->" + iterator.previous().val);
        }
        return builder.toString();
    }
}

Merge Two Sorted Lists

Problem Description
Given 2 Sorted LinkedList, merge them and return a new Sorted LinkedList.
Solution
This problem is a typical operation used in Merge Sort algorithm.
I. Python

view plainprint?

1. # Definition for singly-linked list.  
2. # class ListNode(object):  
3. #     def __init__(self, x):  
4. #         self.val = x  
5. #         self.next = None  
6.   
7. class Solution(object):  
8.     def mergeTwoLists(self, l1, l2):  
9.         """ 
10.         :type l1: ListNode 
11.         :type l2: ListNode 
12.         :rtype: ListNode 
13.         """  
14.         n = ListNode(0)  
15.         current = n  
16.         while l1 and l2:  
17.             if l1.val < l2.val:   
18.                 current.next = l1  
19.                 l1 = l1.next  
20.             else:  
21.                 current.next = l2  
22.                 l2 = l2.next  
23.             current = current.next  
24.               
25.         while l1:  
26.             current.next = l1  
27.             l1 = l1.next  
28.             current = current.next  
29.               
30.         while l2:  
31.             current.next = l2  
32.             l2 = l2.next  
33.             current = current.next  
34.               
35.         return n.next  

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        n = ListNode(0)
        current = n
        while l1 and l2:
            if l1.val < l2.val: 
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
            
        while l1:
            current.next = l1
            l1 = l1.next
            current = current.next
            
        while l2:
            current.next = l2
            l2 = l2.next
            current = current.next
            
        return n.next

II. Java

view plainprint?

1. /** 
2.  * Definition for singly-linked list. 
3.  * public class ListNode { 
4.  *     int val; 
5.  *     ListNode next; 
6.  *     ListNode(int x) { val = x; } 
7.  * } 
8.  */  
9. public class Solution {  
10.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
11.         ListNode n = new ListNode(0);  
12.         ListNode current = n;  
13.         while(l1 != null && l2 != null){  
14.             if (l1.val < l2.val){  
15.                 current.next = l1;  
16.                 l1 = l1.next;  
17.             }else{  
18.                 current.next = l2;  
19.                 l2 = l2.next;  
20.             }  
21.             current = current.next;  
22.         }  
23.         while (l1 != null){  
24.             current.next = l1;  
25.             l1 = l1.next;   
26.             current = current.next;  
27.         }  
28.         while (l2 != null){  
29.             current.next = l2;  
30.             l2 = l2.next;  
31.             current = current.next;  
32.         }  
33.         return n.next;  
34.     }  
35. }  

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

III. C++

view plainprint?

1. /** 
2.  * Definition for singly-linked list. 
3.  * struct ListNode { 
4.  *     int val; 
5.  *     ListNode *next; 
6.  *     ListNode(int x) : val(x), next(NULL) {} 
7.  * }; 
8.  */  
9. class Solution {  
10. public:  
11.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {  
12.         ListNode* n = new ListNode(0);  
13.         ListNode* current = n;  
14.         while (l1 != NULL && l2!= NULL){  
15.             if (l1->val < l2->val){  
16.                 current->next = l1;  
17.                 l1 = l1->next;  
18.             }else{  
19.                 current->next = l2;  
20.                 l2 = l2->next;  
21.             }  
22.             current = current->next;  
23.         }  
24.         while(l1 != NULL){  
25.             current->next = l1;  
26.             l1 = l1->next;  
27.             current = current->next;  
28.         }  
29.         while(l2 != NULL){  
30.             current->next = l2;  
31.             l2 = l2->next;  
32.             current = current->next;  
33.         }  
34.         return n->next;  
35.     }  
36. };  

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

IV. Javascript

view plainprint?

1. /** 
2.  * Definition for singly-linked list. 
3.  * function ListNode(val) { 
4.  *     this.val = val; 
5.  *     this.next = null; 
6.  * } 
7.  */  
8. /** 
9.  * @param {ListNode} l1 
10.  * @param {ListNode} l2 
11.  * @return {ListNode} 
12.  */  
13. var mergeTwoLists = function(l1, l2) {  
14.     var n = new ListNode(0);  
15.     var current = n;  
16.     while(l1 && l2){  
17.         if(l1.val < l2.val) {  
18.             current.next = l1;  
19.             l1 = l1.next;  
20.         }else{  
21.             current.next = l2;  
22.             l2 = l2.next;  
23.         }  
24.         current = current.next;  
25.     }  
26.     while(l1){  
27.         current.next = l1;  
28.         l1 = l1.next;  
29.         current = current.next;  
30.     }  
31.     while(l2){  
32.         current.next = l2;  
33.         l2 = l2.next;  
34.         current = current.next;  
35.     }  
36.     return n.next;  
37. };  

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    var n = new ListNode(0);
    var current = n;
    while(l1 && l2){
        if(l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        }else{
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    while(l1){
        current.next = l1;
        l1 = l1.next;
        current = current.next;
    }
    while(l2){
        current.next = l2;
        l2 = l2.next;
        current = current.next;
    }
    return n.next;
};

Ugly Number II

Problem Description

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Solutions
I. Solution using 3 queues
The idea is that we use three queue to store the ugly numbers.
At first, we add 2, 3, 5 to the first queue, second queue and third queue respectively. Each time we choose the smallest number smallest from one of the 3 queues. If it is from the first queue, we add smallest * 2 to the first queue, smallest * 3 to the second queue, and smallest * 5 to the third queue. If it is from the second queue, we only add smallest * 3 to the second queue, and smallest * 5 to the third queue. And finally, if it is from the third queue, we add smallest * 5 to the third queue. This procedure guarantees that there is no duplicate number in all three queues. We continue doing these steps until we find the n-th number.
We can also solve the problem using min heap.

view plainprint?

1. public class Solution {  
2.     public int nthUglyNumber(int n) {  
3.         if(n==1) return 1;  
4.         Queue<Long> q1 = new LinkedList<Long>();  
5.         Queue<Long> q2 = new LinkedList<Long>();  
6.         Queue<Long> q3 = new LinkedList<Long>();  
7.           
8.         long t = 1;  
9.         q1.add(2L); q2.add(3L); q3.add(5L);  
10.         --n;  
11.         while(n>0){  
12.             if(q1.peek() < q2.peek()){  
13.                 if(q1.peek() < q3.peek()){  
14.                     t = q1.remove();  
15.                     q1.add(t*2); q2.add(t*3); q3.add(t*5);  
16.                 }else {  
17.                     t = q3.remove();  
18.                     q3.add(t*5);  
19.                 }  
20.             }else{  
21.                 if(q2.peek() < q3.peek()){  
22.                     t = q2.remove();  
23.                     q2.add(t*3); q3.add(t*5);  
24.                 }else {  
25.                     t = q3.remove();  
26.                     q3.add(t*5);  
27.                 }  
28.             }  
29.             --n;  
30.         }  
31.         return (int) t;  
32.     }  
33. }  

public class Solution {
    public int nthUglyNumber(int n) {
        if(n==1) return 1;
        Queue<Long> q1 = new LinkedList<Long>();
        Queue<Long> q2 = new LinkedList<Long>();
        Queue<Long> q3 = new LinkedList<Long>();
        
        long t = 1;
        q1.add(2L); q2.add(3L); q3.add(5L);
        --n;
        while(n>0){
            if(q1.peek() < q2.peek()){
                if(q1.peek() < q3.peek()){
                    t = q1.remove();
                    q1.add(t*2); q2.add(t*3); q3.add(t*5);
                }else {
                    t = q3.remove();
                    q3.add(t*5);
                }
            }else{
                if(q2.peek() < q3.peek()){
                    t = q2.remove();
                    q2.add(t*3); q3.add(t*5);
                }else {
                    t = q3.remove();
                    q3.add(t*5);
                }
            }
            --n;
        }
        return (int) t;
    }
}

II. Improvement from the previous code
We now make some improvement on the previous code to make it look better.
Below is the code in Python

view plainprint?

1. class Solution(object):  
2.     def nthUglyNumber(self, n):  
3.         """ 
4.         :type n: int 
5.         :rtype: int 
6.         """  
7.         q1 = [2]  
8.         q2 = [3]  
9.         q3 = [5]  
10.         q = 1  
11.         for i in range(1,n):  
12.             q = min(q1[0], q2[0], q3[0])  
13.             if q == q3[0]:  
14.                 q3.pop(0)  
15.             elif q == q2[0]:  
16.                 q2.pop(0)  
17.                 q2.append(q * 3)  
18.             else:  
19.                 q1.pop(0)  
20.                 q1.append(q * 2)  
21.                 q2.append(q * 3)  
22.                   
23.             q3.append(q * 5) # add to queue 3  
24.         return q  

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        q1 = [2]
        q2 = [3]
        q3 = [5]
        q = 1
        for i in range(1,n):
            q = min(q1[0], q2[0], q3[0])
            if q == q3[0]:
                q3.pop(0)
            elif q == q2[0]:
                q2.pop(0)
                q2.append(q * 3)
            else:
                q1.pop(0)
                q1.append(q * 2)
                q2.append(q * 3)
                
            q3.append(q * 5) # add to queue 3
        return q

And Java Code:

view plainprint?

1. public class Solution {  
2.     public int nthUglyNumber(int n) {  
3.         Queue<Long> q1 = new LinkedList<Long>();    
4.         Queue<Long> q2 = new LinkedList<Long>();    
5.         Queue<Long> q3 = new LinkedList<Long>();  
6.         q1.add(2L); q2.add(3L); q3.add(5L);  
7.           
8.         long q = 1;  
9.         for (int i = 1; i<n; i++){  
10.               
11.             q = Math.min(q1.peek(), Math.min(q2.peek(), q3.peek()));  
12.             if (q == q3.peek())  
13.                 q3.remove();  
14.             else if(q == q2.peek()){  
15.                 q2.remove();  
16.                 q2.add( q * 3);  
17.             }else {  
18.                 q1.remove();  
19.                 q1.add(q * 2);  
20.                 q2.add(q * 3);  
21.             }  
22.             q3.add(q * 5);  
23.         }  
24.           
25.         return (int) q;  
26.     }  
27. }  

public class Solution {
    public int nthUglyNumber(int n) {
        Queue<Long> q1 = new LinkedList<Long>();  
        Queue<Long> q2 = new LinkedList<Long>();  
        Queue<Long> q3 = new LinkedList<Long>();
        q1.add(2L); q2.add(3L); q3.add(5L);
        
        long q = 1;
        for (int i = 1; i<n; i++){
            
            q = Math.min(q1.peek(), Math.min(q2.peek(), q3.peek()));
            if (q == q3.peek())
                q3.remove();
            else if(q == q2.peek()){
                q2.remove();
                q2.add( q * 3);
            }else {
                q1.remove();
                q1.add(q * 2);
                q2.add(q * 3);
            }
            q3.add(q * 5);
        }
        
        return (int) q;
    }
}

III. Reduce space used in the solution numbered II
We can reduce the space used in the previous Solution. Below is the python code.

view plainprint?

1. class Solution(object):  
2.     def nthUglyNumber(self, n):  
3.         """ 
4.         :type n: int 
5.         :rtype: int 
6.         """  
7.         if n == 1: return 1  
8.         p1, p2, p3 = 0, 0, 0 #pointers in the following list  
9.           
10.         q = [0] * n  
11.         q[0] = 1  
12.           
13.         for i in range(1, n):  
14.             t1, t2, t3 = q[p1] * 2, q[p2] * 3, q[p3] * 5  
15.             q[i] = min(t1, t2, t3)  
16.             if q[i] == t1: p1 += 1  
17.             if q[i] == t2: p2 += 1  
18.             if q[i] == t3: p3 += 1  
19.               
20.         return q[-1]  

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 1
        p1, p2, p3 = 0, 0, 0 #pointers in the following list
        
        q = [0] * n
        q[0] = 1
        
        for i in range(1, n):
            t1, t2, t3 = q[p1] * 2, q[p2] * 3, q[p3] * 5
            q[i] = min(t1, t2, t3)
            if q[i] == t1: p1 += 1
            if q[i] == t2: p2 += 1
            if q[i] == t3: p3 += 1
            
        return q[-1]

IV. Using Min Heap
We also can use Min Heap in this problem. Although this approach does not run faster than the above solutions, it is good for us to know how to use additional data structure in order to solve the problem.
Java Code:

view plainprint?

1. public class Solution {  
2.     public int nthUglyNumber(int n) {  
3.   
4.         PriorityQueue<Long> minHeap = new PriorityQueue<Long>();  
5.         minHeap.offer(new Long(1L));  
6.   
7.         Long uglyNumber = 1L;  
8.   
9.         for (int i=1; i<=n; ++i) {  
10.             uglyNumber = minHeap.poll();  
11.             if (!minHeap.contains(uglyNumber * 2))   
12.                 minHeap.offer(uglyNumber * 2);  
13.             if (!minHeap.contains(uglyNumber * 3))   
14.                 minHeap.offer(uglyNumber * 3);  
15.             if (!minHeap.contains(uglyNumber * 5))   
16.                 minHeap.offer(uglyNumber * 5);  
17.         }  
18.   
19.         return  uglyNumber.intValue();  
20.     }  
21. }  

public class Solution {
    public int nthUglyNumber(int n) {

        PriorityQueue<Long> minHeap = new PriorityQueue<Long>();
        minHeap.offer(new Long(1L));

        Long uglyNumber = 1L;

        for (int i=1; i<=n; ++i) {
            uglyNumber = minHeap.poll();
            if (!minHeap.contains(uglyNumber * 2)) 
                minHeap.offer(uglyNumber * 2);
            if (!minHeap.contains(uglyNumber * 3)) 
                minHeap.offer(uglyNumber * 3);
            if (!minHeap.contains(uglyNumber * 5)) 
                minHeap.offer(uglyNumber * 5);
        }

        return  uglyNumber.intValue();
    }
}

Ugly Number

Problem Description

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Solution
We continuously divide the number we need to check by 2, 3, and 5, until that number is not divisible by 2, 3 or 5. If the final result is not equal to 1, the original number is not a ugly number. Otherwise, it is. This is a warm-up exercise for this problem.

view plainprint?

1. public class Solution {  
2.     public boolean isUgly(int num) {  
3.         if(num == 0) return false;  
4.         while(num % 2 == 0) num /=2;  
5.         while(num % 3 == 0) num /= 3;  
6.         while(num % 5 == 0) num /= 5;  
7.         return num == 1;  
8.     }  
9. }  

public class Solution {
    public boolean isUgly(int num) {
        if(num == 0) return false;
        while(num % 2 == 0) num /=2;
        while(num % 3 == 0) num /= 3;
        while(num % 5 == 0) num /= 5;
        return num == 1;
    }
}

Container With Most Water

Problem Description

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.

Solution
In this problem, we use 2 pointers, one runs from the 0, one runs backward.

view plainprint?

1. public class Solution {  
2.     public int maxArea(int[] height) {  
3.         //we assume the array height.length > 0  
4.         int max = 0;  
5.         int area;  
6.         for(int i=0, j=height.length-1; i<j;){  
7.               
8.             if(height[i] > height[j]){  
9.                 area = (j-i) * height[j];  
10.                 j--;  
11.             }else {  
12.                 area = (j-i) * height[i];  
13.                 i++;  
14.             }  
15.             if(area > max) max = area;  
16.         }  
17.         return max;  
18.     }  
19. }  

public class Solution {
    public int maxArea(int[] height) {
        //we assume the array height.length > 0
        int max = 0;
        int area;
        for(int i=0, j=height.length-1; i<j;){
            
            if(height[i] > height[j]){
                area = (j-i) * height[j];
                j--;
            }else {
                area = (j-i) * height[i];
                i++;
            }
            if(area > max) max = area;
        }
        return max;
    }
}

Set Matrix Zeroes

Problem Description
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Solution
At first, I came up with a solution: using the first column and first row to store the information about a row or column should be zero. However, the code is very ugly (See Appendix A). Later, I improved the code by use only the row that we first met an zero to store information about whether the column should be zero. Below is the clean code.

view plainprint?

1. public class Solution {  
2.     public void setZeroes(int[][] matrix) {  
3.   
4.         int m = -1;  
5.         for(int i = 0; i<matrix.length; i++){  
6.             boolean foundZero = false;  
7.             for(int j=0; j<matrix[i].length; j++){  
8.                 if(matrix[i][j] == 0){  
9.                     foundZero = true;  
10.                     break;  
11.                 }  
12.             }  
13.             if(foundZero && m==-1){  
14.                 m = i;  
15.                 continue;  
16.             }  
17.             if(foundZero){  
18.                 for(int j =0;j<matrix[i].length; j++){  
19.                     if(matrix[i][j] == 0) matrix[m][j] = 0;  
20.                     matrix[i][j] = 0;  
21.                 }  
22.             }  
23.         }  
24.         if(m!= -1){  
25.             for(int j = 0; j<matrix[m].length; j++){  
26.                 if(matrix[m][j] == 0)  
27.                 for(int i =0; i<matrix.length; i++)  
28.                     matrix[i][j] = 0;  
29.                 matrix[m][j] = 0;  
30.             }  
31.         }  
32.     }  
33. }  

public class Solution {
    public void setZeroes(int[][] matrix) {

        int m = -1;
        for(int i = 0; i<matrix.length; i++){
            boolean foundZero = false;
            for(int j=0; j<matrix[i].length; j++){
                if(matrix[i][j] == 0){
                    foundZero = true;
                    break;
                }
            }
            if(foundZero && m==-1){
                m = i;
                continue;
            }
            if(foundZero){
                for(int j =0;j<matrix[i].length; j++){
                    if(matrix[i][j] == 0) matrix[m][j] = 0;
                    matrix[i][j] = 0;
                }
            }
        }
        if(m!= -1){
            for(int j = 0; j<matrix[m].length; j++){
                if(matrix[m][j] == 0)
                for(int i =0; i<matrix.length; i++)
                    matrix[i][j] = 0;
                matrix[m][j] = 0;
            }
        }
    }
}

Appendix A: How ugly it was

view plainprint?

1. public class Solution {  
2.     public void setZeroes(int[][] matrix) {  
3.           
4.         boolean firstRowZero = false;  
5.         boolean firstColZero = false;  
6.           
7.         for(int i =0; i<matrix.length; i++)  
8.             if(matrix[i][0] == 0) {  
9.                 firstColZero = true;  
10.                 break;  
11.             }  
12.               
13.         for(int i =0; i<matrix[0].length; i++)  
14.             if(matrix[0][i] == 0) {  
15.                 firstRowZero = true;  
16.                 break;  
17.             }  
18.                   
19.         for(int i = 1; i<matrix.length; i++){  
20.             for(int j = 1; j<matrix[0].length; j++){  
21.                 if(matrix[i][j] == 0){  
22.                     matrix[i][0] = 0;  
23.                     matrix[0][j] = 0;  
24.                 }  
25.             }  
26.         }  
27.           
28.         for(int i=1; i<matrix.length; i++){  
29.             if(matrix[i][0] == 0)  
30.             for(int j=1; j<matrix[0].length; j++){  
31.                 matrix[i][j] = 0;  
32.             }  
33.         }  
34.         for(int i=1; i<matrix[0].length; i++){  
35.             if(matrix[0][i] == 0)  
36.             for(int j=1; j<matrix.length; j++){  
37.                 matrix[j][i] = 0;  
38.             }  
39.         }  
40.           
41.         if (firstRowZero)  
42.             for(int i =0; i<matrix[0].length; i++)  
43.                 matrix[0][i] = 0;  
44.         if (firstColZero)  
45.             for(int i=0; i<matrix.length; i++)  
46.                 matrix[i][0] = 0;  
47.     }  
48. }  

public class Solution {
    public void setZeroes(int[][] matrix) {
        
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        for(int i =0; i<matrix.length; i++)
            if(matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
            
        for(int i =0; i<matrix[0].length; i++)
            if(matrix[0][i] == 0) {
                firstRowZero = true;
                break;
            }
                
        for(int i = 1; i<matrix.length; i++){
            for(int j = 1; j<matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for(int i=1; i<matrix.length; i++){
            if(matrix[i][0] == 0)
            for(int j=1; j<matrix[0].length; j++){
                matrix[i][j] = 0;
            }
        }
        for(int i=1; i<matrix[0].length; i++){
            if(matrix[0][i] == 0)
            for(int j=1; j<matrix.length; j++){
                matrix[j][i] = 0;
            }
        }
        
        if (firstRowZero)
            for(int i =0; i<matrix[0].length; i++)
                matrix[0][i] = 0;
        if (firstColZero)
            for(int i=0; i<matrix.length; i++)
                matrix[i][0] = 0;
    }
}

Appendix B: Python Code for the good solution

view plainprint?

1. class Solution(object):  
2.     def setZeroes(self, matrix):  
3.         """ 
4.         :type matrix: List[List[int]] 
5.         :rtype: void Do not return anything, modify matrix in-place instead. 
6.         """  
7.         m = -1  
8.         for i in range(len(matrix)):  
9.             found = False  
10.             for j in range(len(matrix[0])):  
11.                 if matrix[i][j] == 0:  
12.                     found = True  
13.                     break  
14.             if found and m==-1:  
15.                 m = i  
16.                 continue  
17.             if found:  
18.                 for j in range(len(matrix[i])):  
19.                     if matrix[i][j] == 0:  
20.                         matrix[m][j] = 0  
21.                     matrix[i][j] = 0  
22.           
23.         if m!=-1:          
24.             for j in range(len(matrix[m])):  
25.                 if matrix[m][j] == 0:  
26.                     for i in range(0, len(matrix)):  
27.                         matrix[i][j] = 0  
28.                 matrix[m][j] = 0  

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        m = -1
        for i in range(len(matrix)):
            found = False
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    found = True
                    break
            if found and m==-1:
                m = i
                continue
            if found:
                for j in range(len(matrix[i])):
                    if matrix[i][j] == 0:
                        matrix[m][j] = 0
                    matrix[i][j] = 0
        
        if m!=-1:        
            for j in range(len(matrix[m])):
                if matrix[m][j] == 0:
                    for i in range(0, len(matrix)):
                        matrix[i][j] = 0
                matrix[m][j] = 0

Palindrome Linked List

Problem Description

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

NOTE: the LinkedList is defined as below (In java code):

Solutions

In this problem, we count the LinkedList length. Then we reverse the second half of the LinkedList, compare with the first half, and finally reverse the second half again.
NOTE: In the implementation, the "middle" is not the actually middle of the linked list. It is one node before the actual middle node. This makes the coding easier and shorter.

view plainprint?

1. class Solution:  
2.     # @param {ListNode} head  
3.     # @return {boolean}  
4.     def isPalindrome(self, head):  
5.         if  head == None: return True  
6.         #-----------------Count the linked list's length-------------  
7.           
8.         lens = self.length_of(head)  
9.         #------------------------------------------------------------  
10.         if lens == 1 : return True  
11.           
12.         #reverse the second half  
13.         half = (lens+1)/2  
14.           
15.         #Find the middle  
16.         middle = head  
17.         i = 1  
18.         while i<half:  
19.             i += 1  
20.             middle = middle.next  
21.               
22.         self.reverse(middle)  
23.           
24.         #compare  
25.         current1 = head  
26.         current2 = middle.next  
27.         for i in range(lens/2):  
28.             if current1.val != current2.val: return False  
29.             current1 = current1.next  
30.             current2 = current2.next  
31.           
32.         #reverse the list back  
33.         self.reverse(middle)  
34.           
35.         return True  
36.       
37.     def length_of(self, head):  
38.         lens= 0  
39.         current = head  
40.         while current:  
41.             lens += 1  
42.             current = current.next  
43.         return lens  
44.               
45.     def reverse(self, head):  
46.         if head is None: return  
47.         #reverse all elements after head, not include head  
48.         current = head.next  
49.         head.next = None  
50.           
51.         while current != None:  
52.             temp = current.next  
53.             current.next = head.next  
54.             head.next = current  
55.             current = temp  

class Solution:
    # @param {ListNode} head
    # @return {boolean}
    def isPalindrome(self, head):
        if  head == None: return True
        #-----------------Count the linked list's length-------------
        
        lens = self.length_of(head)
        #------------------------------------------------------------
        if lens == 1 : return True
        
        #reverse the second half
        half = (lens+1)/2
        
        #Find the middle
        middle = head
        i = 1
        while i<half:
            i += 1
            middle = middle.next
            
        self.reverse(middle)
        
        #compare
        current1 = head
        current2 = middle.next
        for i in range(lens/2):
            if current1.val != current2.val: return False
            current1 = current1.next
            current2 = current2.next
        
        #reverse the list back
        self.reverse(middle)
        
        return True
    
    def length_of(self, head):
        lens= 0
        current = head
        while current:
            lens += 1
            current = current.next
        return lens
            
    def reverse(self, head):
        if head is None: return
        #reverse all elements after head, not include head
        current = head.next
        head.next = None
        
        while current != None:
            temp = current.next
            current.next = head.next
            head.next = current
            current = temp

II. Solution without counting LinkedList's length
In this solution, we use 2 points, one runs through 1 element, the other runs through 2 elements at a time.

view plainprint?

1. class Solution:  
2.     # @param {ListNode} head  
3.     # @return {boolean}  
4.     def isPalindrome(self, head):  
5.           
6.         slow = ListNode(0)  
7.         fast = slow  
8.         slow.next = head  
9.         while fast and fast.next:  
10.             slow = slow.next  
11.             fast = fast.next.next  
12.           
13.         self.reverse(slow)  
14.           
15.         #compare  
16.         current1 = head  
17.         current2 = slow.next  
18.         while current2:  
19.             if current1.val != current2.val: return False  
20.             current1 = current1.next  
21.             current2 = current2.next  
22.           
23.         #reverse the list back  
24.         self.reverse(slow)  
25.           
26.         return True  
27.               
28.     def reverse(self, head):  
29.         if head is None: return  
30.         #reverse all elements after head, not include head  
31.         current = head.next  
32.         head.next = None  
33.           
34.         while current != None:  
35.             temp = current.next  
36.             current.next = head.next  
37.             head.next = current  
38.             current = temp          

class Solution:
    # @param {ListNode} head
    # @return {boolean}
    def isPalindrome(self, head):
        
        slow = ListNode(0)
        fast = slow
        slow.next = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        self.reverse(slow)
        
        #compare
        current1 = head
        current2 = slow.next
        while current2:
            if current1.val != current2.val: return False
            current1 = current1.next
            current2 = current2.next
        
        #reverse the list back
        self.reverse(slow)
        
        return True
            
    def reverse(self, head):
        if head is None: return
        #reverse all elements after head, not include head
        current = head.next
        head.next = None
        
        while current != None:
            temp = current.next
            current.next = head.next
            head.next = current
            current = temp        

Maximum Rectangle

Problem Description
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Solutions
I. Solution by finding largest rectangle in histogram

view plainprint?

1. class Solution:  
2.     # @param matrix, a list of lists of 1 length string  
3.     # @return an integer  
4.     def maximalRectangle(self, matrix):  
5.         if not matrix:  
6.             return 0  
7.         h, w = len(matrix), len(matrix[0])  
8.         m = [[0]*w for _ in range(h)]  
9.         for j in range(h):  
10.             for i in range(w):  
11.                 if matrix[j][i] == '1':  
12.                     m[j][i] = m[j-1][i] + 1  
13.         return max(self.largestRectangleArea(row) for row in m)  
14.       
15.     def largestRectangleArea(self, height):  
16.         ''''' 
17.         This uses the way we calculate maximum rectangle in histogram 
18.         '''  
19.         height.append(0)  
20.         stack, area = [], 0  
21.         for i in range(len(height)):  
22.             while stack and height[stack[-1]] > height[i]:  
23.                 h = height[stack.pop()]  
24.                 w = i if not stack else i-stack[-1]-1  
25.                 area = max(area, h*w)  
26.             stack.append(i)  
27.         return area  

class Solution:
    # @param matrix, a list of lists of 1 length string
    # @return an integer
    def maximalRectangle(self, matrix):
        if not matrix:
            return 0
        h, w = len(matrix), len(matrix[0])
        m = [[0]*w for _ in range(h)]
        for j in range(h):
            for i in range(w):
                if matrix[j][i] == '1':
                    m[j][i] = m[j-1][i] + 1
        return max(self.largestRectangleArea(row) for row in m)
    
    def largestRectangleArea(self, height):
        '''
        This uses the way we calculate maximum rectangle in histogram
        '''
        height.append(0)
        stack, area = [], 0
        for i in range(len(height)):
            while stack and height[stack[-1]] > height[i]:
                h = height[stack.pop()]
                w = i if not stack else i-stack[-1]-1
                area = max(area, h*w)
            stack.append(i)
        return area

Largest Rectangle in Histogram

Problem Description
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example,
Given height = [2,1,5,6,2,3],
return 10.
Solutions
I. Using stack:
The idea is using stack to store non-decreasing elements.

view plainprint?

1. class Solution:  
2.     # @param {integer[]} height  
3.     # @return {integer}  
4.     def largestRectangleArea(self, height):  
5.         height.append(0)  
6.         stack, area = [], 0  
7.         for i in range(len(height)):  
8.             while stack and height[stack[-1]] > height[i]:  
9.                 h = height[stack.pop()]  
10.                 w = i if not stack else i-stack[-1]-1  
11.                 area = max(area, h*w)  
12.             stack.append(i)  
13.         return area  

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def largestRectangleArea(self, height):
        height.append(0)
        stack, area = [], 0
        for i in range(len(height)):
            while stack and height[stack[-1]] > height[i]:
                h = height[stack.pop()]
                w = i if not stack else i-stack[-1]-1
                area = max(area, h*w)
            stack.append(i)
        return area

Further Discussion
This is a pretty interesting problem. It has many applications, one of which you can see in this post.
We also can expand the problem to some other problems. Can you solve the following problems? Please post a comment to discuss ^_^.
A. Find the largest rectangle in this special "Historgram"
We expand the histogram to both directions - positive and negative, as in the picture below.

B. Find the largest box in 3-d Histogram
The original problem is a 2D histogram. Suppose we have 3D histogram, can we find the box with maximum volume?

Valid Parentheses

Problem Description

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.

Solution

This is an easy solution using stack.

view plainprint?

1. class Solution:  
2.     # @param {string} s  
3.     # @return {boolean}  
4.     def isValid(self, s):  
5.         dic = {')':'(', '}':'{', ']':'['}  
6.         stack = []  
7.         for p in s:  
8.             if p not in dic:  
9.                 stack.append(p)  
10.             elif not stack or dic[p] != stack.pop(-1):  
11.                 return False  
12.         return not stack  

class Solution:
    # @param {string} s
    # @return {boolean}
    def isValid(self, s):
        dic = {')':'(', '}':'{', ']':'['}
        stack = []
        for p in s:
            if p not in dic:
                stack.append(p)
            elif not stack or dic[p] != stack.pop(-1):
                return False
        return not stack

Distinct Subsequences

Problem Description

Given a string S and a string T, count the number of distinct sub-sequences of T in S.

A sub-sequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

NOTE: The above problem statement is not very clear. We can make it "cleaner" by re-stating the problem as:
Given a string S and a string T, counting the number of ways that we remove some (or none) characters in S to get the remaining string equal to T.

Solutions

For a string str, we denote str[0,j] is the sub-string of str from index 0 to j inclusively. We easily guess that this solution can be solved by Dynamic Programming.
If we call dp[i][j] is the number of ways to remove some characters from S[0,i] to get T[0,j], we have the recursive formula:
dp [i][j] = dp[i-1][j] if S[i] != T[j] , or
dp [i][j] = dp[i-1][j] + dp[i-1][j-1] if S[i] ==T[j]

Therefore, we can come up with solution I), and improve it on II).

I. O(m*n) space

view plainprint?

1. public class Solution {  
2.     public int numDistinct(String s, String t) {  
3.         if(s.length()==0 || s == null || t == null || t.length() == 0) return 0;  
4.         int[][] dp = new int[s.length()][t.length()];  
5.           
6.         char c = t.charAt(0);  
7.         for(int i=0; i<s.length(); i++){  
8.             dp[i][0] = (i==0? 0: dp[i-1][0]) + (s.charAt(i)==c?1:0);  
9.         }  
10.         for(int i = 1; i<s.length(); i++){  
11.             c = s.charAt(i);  
12.             for(int j=1; j<t.length(); j++){  
13.                 dp[i][j] = dp[i-1][j] + (t.charAt(j)==c?dp[i-1][j-1]:0);  
14.             }  
15.         }  
16.         return dp[s.length()-1][t.length()-1];  
17.     }  
18. }  

public class Solution {
    public int numDistinct(String s, String t) {
        if(s.length()==0 || s == null || t == null || t.length() == 0) return 0;
        int[][] dp = new int[s.length()][t.length()];
        
        char c = t.charAt(0);
        for(int i=0; i<s.length(); i++){
            dp[i][0] = (i==0? 0: dp[i-1][0]) + (s.charAt(i)==c?1:0);
        }
        for(int i = 1; i<s.length(); i++){
            c = s.charAt(i);
            for(int j=1; j<t.length(); j++){
                dp[i][j] = dp[i-1][j] + (t.charAt(j)==c?dp[i-1][j-1]:0);
            }
        }
        return dp[s.length()-1][t.length()-1];
    }
}

II. O(n) space where n is length of T
We see that the formula of dp[i][j] refer to only dp[i-1][j] and dp[i-1][j-1]. This gives us the idea that we can reduce the space to O(n).
Since we need to make use of dp[i-1][j-1], we run backward!!!

view plainprint?

1. public class Solution {  
2.     public int numDistinct(String s, String t) {  
3.         if(s == null || t == null || t.length() == 0) return 0;  
4.         int[] dp = new int[t.length()];  
5.           
6.         for(int i = 0; i<s.length(); i++){  
7.             char c = s.charAt(i);  
8.             for(int j=dp.length-1; j>=0; j--){  
9.                 if(c == t.charAt(j)){  
10.                     dp[j] = dp[j] + (j!=0?dp[j-1]: 1);  
11.                 }  
12.             }  
13.         }  
14.         return dp[t.length()-1];  
15.     }  
16. }  

public class Solution {
    public int numDistinct(String s, String t) {
        if(s == null || t == null || t.length() == 0) return 0;
        int[] dp = new int[t.length()];
        
        for(int i = 0; i<s.length(); i++){
            char c = s.charAt(i);
            for(int j=dp.length-1; j>=0; j--){
                if(c == t.charAt(j)){
                    dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
                }
            }
        }
        return dp[t.length()-1];
    }
}

House Robber : Part 1

Problem Description

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.

Solutions

This problem is a typical dynamic programming problem. Here I just want to explain a little bit for those who are at the beginning of the long journey - programming every day! (For those who are familiar with DP, you can take a look at some solutions below, they might be useful for you ^_^.)

In dynamic programming problem, all we need to do is to find the recursion function. In many difficult problems, it is very hard to find the recursion functions. However, in this problem, it is pretty easy.

All you need to think is: which function we should choose in this problem? 

A typical thinking when encountering this problem is: we have some f(n) if array is of length n. How f(n+1) is calculated if array is of length (n+1)?

suppose the array is of length n, and the maximum amount of money you can rob is f(n). We need to make another condition here: we must rob the last house in that array! Why do we need this? To make it easy to calculate the function recursively. Yes it is.

I will list the recursion relation here, and you will think why:

f(n+3) = A[n+3] + max ( f(n+1) , f(n)) , where A is 1-based array of amounts of money you can rob.

And we can put this into code in java & python as below

I. Java

view plainprint?

1. public class Solution {  
2.     public int rob(int[] nums) {  
3.         int n = nums.length;  
4.         if (n == 0) return 0;  
5.         if (n == 1) return nums[0];  
6.         if (n > 2)  
7.             nums[2] += nums[0];  
8.         for (int i = 3; i<nums.length; i++){  
9.             nums[i] += Math.max(nums[i-2], nums[i-3]);  
10.         }  
11.         return Math.max(nums[n-1], nums[n-2]);  
12.     }     
13. }  

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n > 2)
            nums[2] += nums[0];
        for (int i = 3; i<nums.length; i++){
            nums[i] += Math.max(nums[i-2], nums[i-3]);
        }
        return Math.max(nums[n-1], nums[n-2]);
    }   
}

II. Python

view plainprint?

1. class Solution:  
2.     # @param {integer[]} nums  
3.     # @return {integer}  
4.     def rob(self, nums):  
5.         n = len(nums)  
6.         if n == 0: return 0  
7.         if n == 1: return nums[0]  
8.         if n > 2:  
9.             nums[2] += nums[0]  
10.         for i in range(3, n):  
11.             nums[i] += max(nums[i-2], nums[i-3])  
12.               
13.         return max(nums[n-1], nums[n-2])  

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        if n > 2:
            nums[2] += nums[0]
        for i in range(3, n):
            nums[i] += max(nums[i-2], nums[i-3])
            
        return max(nums[n-1], nums[n-2])

III. Python - 3 line version
You might not satisfied with the above the solutions. But thhe following code is too simple that makes me fall in love with python forever!

view plainprint?

1. class Solution:  
2.     # @param {integer[]} nums  
3.     # @return {integer}  
4.     def rob(self, nums):  
5.         first, second = 0, 0  
6.         for i in nums: first, second = second, max(first + i, second)  
7.         return second  

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        first, second = 0, 0
        for i in nums: first, second = second, max(first + i, second)
        return second

NOTE: the above code is based on the following formula:

view plainprint?

1. f(0) = nums[0]  
2. f(1) = max(nums[0], nums[1])  
3. f(k) = max( f(k-2) + nums[k], f(k-1) )  

f(0) = nums[0]
f(1) = max(nums[0], nums[1])
f(k) = max( f(k-2) + nums[k], f(k-1) )

IV. Java version of the 3-line python version

view plainprint?

1. public class Solution {  
2.   
3.     public int rob(int[] num) {  
4.         int first = 0; int second = 0; int t;  
5.         for (int n :num) {  
6.             t = second;  
7.             second = Math.max(first + n, second);  
8.             first = t;  
9.         }  
10.         return second;          
11.     }  
12. }  

public class Solution {

    public int rob(int[] num) {
        int first = 0; int second = 0; int t;
        for (int n :num) {
            t = second;
            second = Math.max(first + n, second);
            first = t;
        }
        return second;        
    }
}

Jump Game

Problem Description

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.

Solutions

The idea is obvious. We use dynamic programming technique, and scan the array forward or backward. Needless to say, the code has just a few lines.
I. Scanning Backward

view plainprint?

1. class Solution:  
2.     # @param {integer[]} nums  
3.     # @return {boolean}  
4.     def canJump(self, nums):  
5.         n = len(nums)  
6.         last = n-1  
7.         for i in range(2,n+1):  
8.             if n-i + nums[-i] >= last:  
9.                 last = n-i  
10.         return last == 0  

class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def canJump(self, nums):
        n = len(nums)
        last = n-1
        for i in range(2,n+1):
            if n-i + nums[-i] >= last:
                last = n-i
        return last == 0

II. Scanning Forward

view plainprint?

1. class Solution:  
2.     # @param {integer[]} nums  
3.     # @return {boolean}  
4.     def canJump(self, nums):  
5.         reachable = 0  
6.         for i in range(len(nums)):  
7.             if i > reachable: return False  
8.             reachable = max(reachable, i+nums[i])  
9.         return True  

class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def canJump(self, nums):
        reachable = 0
        for i in range(len(nums)):
            if i > reachable: return False
            reachable = max(reachable, i+nums[i])
        return True

Unique Paths: Part 2

Problem Description

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

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

The total number of unique paths is 2.

Note: m and n will be at most 100.

Solutions

The solution for this problem is also pretty obvious. In the previous part, we examine dynamic solutions and combinatoric solution. However, in this problem, we are no longer able  to use the combinatoric solution! Below is just a dynamic solution in python.

view plainprint?

1. class Solution:  
2.     # @param {integer[][]} obstacleGrid  
3.     # @return {integer}  
4.     def uniquePathsWithObstacles(self, obstacleGrid):  
5.           
6.         m = len(obstacleGrid)  
7.         n = len(obstacleGrid[0])  
8.         a = [0] * (n+1)  
9.         a[-1] = 1  
10.           
11.         for i in range(1,n+1):  
12.             if obstacleGrid[m-1][-i] == 0:  
13.                 a[n-i] = a[n-i+1]  
14.           
15.         a[-1] = 0  
16.         for j in range(2, m+1):  
17.             for i in range(1, n+1):  
18.                 if obstacleGrid[m-j][-i] == 0:  
19.                     a[n-i] += a[n-i + 1]  
20.                 else:  
21.                     a[n-i] = 0  
22.         return a[0]  

class Solution:
    # @param {integer[][]} obstacleGrid
    # @return {integer}
    def uniquePathsWithObstacles(self, obstacleGrid):
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        a = [0] * (n+1)
        a[-1] = 1
        
        for i in range(1,n+1):
            if obstacleGrid[m-1][-i] == 0:
                a[n-i] = a[n-i+1]
        
        a[-1] = 0
        for j in range(2, m+1):
            for i in range(1, n+1):
                if obstacleGrid[m-j][-i] == 0:
                    a[n-i] += a[n-i + 1]
                else:
                    a[n-i] = 0
        return a[0]

Unique Paths : Part 1

Problem Description
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solutions:
This is a typical problem using dynamic programming. However, this problem is the first level of dynamic programming problems! All you need is to find out the recursive relation, and implement it!
NOTE: small m & n would suggest us that this is a dynamic programming problem. However, since m & n are too small, it suggests that we can solve the problem using another method! Let's look at the 3rd solution for it ^_^
I. Simple Solution

view plainprint?

1. class Solution:  
2.     # @param {integer} m  
3.     # @param {integer} n  
4.     # @return {integer}  
5.     def uniquePaths(self, m, n):  
6.         a = [[0] * (n+2) for i in range(m+1)]  
7.           
8.         for i in range(1, n+1):  
9.             a[m][i] = 1  
10.         for i in range(1,m):  
11.             for j in range(0,n):  
12.                 a[m-i][n-j] = a[m-i+1][n-j] + a[m-i][n-j+1]  
13.                   
14.         return a[1][1]  

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        a = [[0] * (n+2) for i in range(m+1)]
        
        for i in range(1, n+1):
            a[m][i] = 1
        for i in range(1,m):
            for j in range(0,n):
                a[m-i][n-j] = a[m-i+1][n-j] + a[m-i][n-j+1]
                
        return a[1][1]

II. Improvement on Solution time & Space Complexity
In this solution, we use less space than the above solution.

view plainprint?

1. class Solution:  
2.     # @param {integer} m  
3.     # @param {integer} n  
4.     # @return {integer}  
5.     def uniquePaths(self, m, n):  
6.         a = [ 1 for i in range(n)]  
7.           
8.         for j in range(1, m):  
9.             for i in range(1,n):  
10.                 a[i] += a[i-1]  
11.         return a[n-1]  

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        a = [ 1 for i in range(n)]
        
        for j in range(1, m):
            for i in range(1,n):
                a[i] += a[i-1]
        return a[n-1]

III. Combinatoric Solution
We see that the robot is standing at location (1,1), and it wants to move to location (m,n). So in total, it needs to move (m-1) steps downwards, and (n-1) steps rightwards, in any orders! If we mark going down as 1, and going to the right as 0, we have a string of length (m+n-2) which consists of 1 and 0. So you guess it, there are how many strings like that? Yes, it is (m+n-2)!/[(n-1)!*(m-1)!]

view plainprint?

1. class Solution:  
2.     # @param {integer} m  
3.     # @param {integer} n  
4.     # @return {integer}  
5.     def uniquePaths(self, m, n):  
6.         # we assume m, n >= 1  
7.         if m == 1 or n == 1: return 1  
8.           
9.         m -= 1  
10.         n -= 1  
11.         if m > n:  
12.             t = m  
13.             m = n  
14.             n = t  
15.           
16.         result = 1  
17.         for i in range(1,m+1):  
18.             result *= (n + i)  
19.             result /= i  

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        # we assume m, n >= 1
        if m == 1 or n == 1: return 1
        
        m -= 1
        n -= 1
        if m > n:
            t = m
            m = n
            n = t
        
        result = 1
        for i in range(1,m+1):
            result *= (n + i)
            result /= i

Calculate x to the power of n

Problem Description
Implement pow(x, n) where x is a float and n is an integer.

Solutions
Analysis: This problem is pretty simple. We can calculate it in O(n) time. But we can also easily do it in O(log n ) time.

I. Recursive Solution - O(log n)

view plainprint?

1. class Solution:  
2.     # @param {float} x  
3.     # @param {integer} n  
4.     # @return {float}  
5.     def myPow(self, x, n):  
6.         if n == 0: return 1  
7.         result = self.myPow(x, n/2) if n>0 else self.myPow(1/x, -(n/2))  
8.         return result * result * (x if n % 2 == 1 else 1)  

class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        result = self.myPow(x, n/2) if n>0 else self.myPow(1/x, -(n/2))
        return result * result * (x if n % 2 == 1 else 1)

II. Non-recursive Solution - O(log n) time - O(log n) space
This solution use one additional array, which is quite obvious.

view plainprint?

1. class Solution:  
2.     # @param {float} x  
3.     # @param {integer} n  
4.     # @return {float}  
5.     def myPow(self, x, n):  
6.         if n == 0: return 1  
7.         result = 1  
8.         a = []  
9.         t = n if n>0 else -n  
10.           
11.         while t > 0:  
12.             a.append(t % 2)  
13.             t = t >> 1  
14.         for i in range(1,len(a)+1):  
15.             result = result * result * (1 if a[-i] == 0 else x)  
16.           
17.         if n <0 : result = 1.0 / result  
18.         return result  

class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        result = 1
        a = []
        t = n if n>0 else -n
        
        while t > 0:
            a.append(t % 2)
            t = t >> 1
        for i in range(1,len(a)+1):
            result = result * result * (1 if a[-i] == 0 else x)
        
        if n <0 : result = 1.0 / result
        return result

III. Non-recursive Solution - O(log n) time - O(1) space
This is an improvement on the solution numbered II.

view plainprint?

1. class Solution:  
2.     # @param {float} x  
3.     # @param {integer} n  
4.     # @return {float}  
5.     def myPow(self, x, n):  
6.         if n == 0: return 1  
7.         m = n  
8.         if n < 0:  
9.             m = -m  
10.             x = 1/x  
11.           
12.         result = 1  
13.         while m > 0:  
14.               
15.             if (m & 1) == 1:  
16.                 result *= x  
17.             x *= x  
18.             m >>=1  
19.               
20.         return result    

class Solution:
    # @param {float} x
    # @param {integer} n
    # @return {float}
    def myPow(self, x, n):
        if n == 0: return 1
        m = n
        if n < 0:
            m = -m
            x = 1/x
        
        result = 1
        while m > 0:
            
            if (m & 1) == 1:
                result *= x
            x *= x
            m >>=1
            
        return result