Perfect Squares [LeetCode]

Problem Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solutions

I. Dynamic Programming
This problem can be solved by dynamic programming. If we call dp is the array of least numbers of perfect square numbers for each integer from 1 to n, we have the following relation:
dp[n] = 1 + min (dp[n-i*i] for i from 1 to square root of n)
However, (as of 2015-09-09) I saw people complain that the dynamic programming solution got Time Limit Exception (TLE) with Python. Therefore, StefanPochmann, a member of LeetCode, solved the solution by using "Static" dynamic programming. That means the array dp is a static variable of the class Solution.
Dynamic Programming C++ Code

int numSquares(int n) {
    static vector<int> dp {0};
    while (dp.size() <= n) {
        int m = dp.size(), squares = INT_MAX;
        for (int i=1; i*i<=m; ++i)
            squares = min(squares, dp[m-i*i] + 1);
        dp.push_back(squares);
    }
    return dp[n];
}

Dynamic Programming C++ : Reverse for-loops inside out

int numSquares(int n) {
    static vector<int> dp {0};
    int m = dp.size();
    dp.resize(max(m, n+1), INT_MAX);
    for (int i=1, i2; (i2 = i*i)<=n; ++i)
        for (int j=max(m, i2); j<=n; ++j)
            if (dp[j] > dp[j-i2] + 1)
                dp[j] = dp[j-i2] + 1;
    return dp[n];
}

Dynamic Programming Python Code

class Solution(object):
    _dp = [0]
    def numSquares(self, n):
        dp = self._dp
        while len(dp) <= n:
            dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
        return dp[n]

Dynamic Programming Ruby Code

$dp = [0]
def num_squares(n)
  $dp << (1..$dp.size**0.5).map { |i| $dp[-i*i] }.min + 1 until $dp[n]
  $dp[n]
end

However, in Python, if you test that code with test case 1,000,000, you will get the TLE error.
NOTE: I'm very happy that LeetCode now provides testing against custom input (From 2015-09-09). This feature I've seen in Hackerrank and wanted LeetCode to implemente it for quite a long time ago.

II. Breadth First Search

Picture 1: Graph of numbers 

In this problem, we define a graph where each number from 0 to n is a node. Two numbers p < q is connected if (q-p) is a perfect square.

So we can simply do a Breadth First Search from the node 0.

Below is the Python code that even can pass the custom test case of 1,000,000.

Breadth First Search Python Code

class Solution(object):
    _dp = [0]
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
       
        q1 = [0]
        q2 = []
        level = 0
        visited = [False] * (n+1)
        while True:
            level += 1
            for v in q1:
                i = 0
                while True:
                    i += 1
                    t = v + i * i
                    if t == n: return level
                    if t > n: break
                    if visited[t]: continue
                    q2.append(t)
                    visited[t] = True
            q1 = q2
            q2 = []
                
        return 0

PS: For now, I do not have very much time to write the code in Java, C++, C#, Javacript or Ruby, so you are extremely welcome to post your solutions as a comment!

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"!

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)

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.

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

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:

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.

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:

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

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

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

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

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!!!

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

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

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!

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:

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

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

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

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.

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

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.

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)!]

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