Leetcode: Perfect Squares

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.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Understand the problem:
This is a DP problem.

-- Define dp[n + 1], where dp[i] means the least number of perfect square numbers for integer i.
-- Initialization. dp[0] = 0. dp[i] = Integer.MAX_VALUE since we calculate the min number
-- Transit function, dp[i] = min(dp[i], dp[i - j * j]), where j * j <= i
-- Final state: dp[n]

Code (Java):

public class Solution {
    public int numSquares(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        return dp[n];
    }
}

Leetcode: Paint Fence

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

Understand the problem:
We can use a DP solution. 
  -- Define two DP arrays, diff[n] and same[i]. Where diff[i] means the number of ways for the fence i which has different color with fence i -1. same[i] means the number of ways if fence i has the same color with fence i - 1. 
 --  Initialization same[0] = 0, diff[0] = k.
 -- same[i] = diff[i - 1]. 
 -- diff[i] = (k - 1) * (same[i - 1] + diff[i - 1]);

 -- Final state: same[n - 1] + diff[n - 1]. 

Code (Java):

public class Solution {
    public int numWays(int n, int k) {
        if (n <= 0 || k <= 0) {
            return 0;
        }
        
        if (n == 1) {
            return k;
        }
        
        // i -1 and i -2 with the same color
        int[] dp1 = new int[n];
        // i - 1 and i - 2 with diff. color
        int[] dp2 = new int[n];
        
        // Initializaiton
        dp1[0] = 0;
        dp2[0] = k;
        
        for (int i = 1; i < n; i++) {
            dp1[i] = dp2[i - 1];
            dp2[i] = (k - 1) * (dp1[i - 1] + dp2[i - 1]);
        }
        
        // Final state
        return dp1[n - 1] + dp2[n - 1];
    }
}

A Constant Space solution:

public class Solution {
    public int numWays(int n, int k) {
        if (n <= 0 || k <= 0) {
            return 0;
        }
        
        if (n == 1) {
            return k;
        }
        
        int preSame = 0;
        int preDiff = k;
        
        for (int i = 1; i < n; i++) {
            int same = preDiff;
            int diff = (k - 1) * (preSame + preDiff);
            
            preSame = same;
            preDiff = diff;
        }
        
        return preSame + preDiff;
    }
}

Leetcode: Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

Understand the problem:
This is a classic back pack problem. 
 -- Define dp[n][k], where dp[i][j] means for house i with color j the minimum cost. 
 -- Initial value: dp[0][j] = costs[0][j]. For others, dp[i][j] = Integer.MAX_VALUE;, i >= 1
 -- Transit function: dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + cost[i][j]), where k != j.
 -- Final state: Min(dp[n - 1][k]).

Code (Java):

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        
        // dp[i][j] means the min cost painting for house i, with color j
        int[][] dp = new int[n][k];
        
        // Initialization
        for (int i = 0; i < k; i++) {
            dp[0][i] = costs[0][i];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int m = 0; m < k; m++) {
                    if (m != j) {
                        dp[i][j] = Math.min(dp[i - 1][m] + costs[i][j], dp[i][j]);
                    }
                }
            }
        }
        
        // Final state
        int minCost = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            minCost = Math.min(minCost, dp[n - 1][i]);
        }
        
        return minCost;
    }
}

Analysis: 
Time complexity: O(n*k*k).
Space complexity: O(n*k).

A O(k) Space Solution:
Since dp[i][k] only depends on dp[i-1][j], we can use a 1-D DP solution. 

Code (Java):

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        
        // dp[j] means the min cost for color j
        int[] dp1 = new int[k];
        int[] dp2 = new int[k];
        
        // Initialization
        for (int i = 0; i < k; i++) {
            dp1[i] = costs[0][i];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp2[j] = Integer.MAX_VALUE;
                for (int m = 0; m < k; m++) {
                    if (m != j) {
                        dp2[j] = Math.min(dp1[m] + costs[i][j], dp2[j]);
                    }
                }
            }
            
            for (int j = 0; j < k; j++) {
                dp1[j] = dp2[j];
            }
        }
        
        // Final state
        int minCost = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            minCost = Math.min(minCost, dp1[i]);
        }
        
        return minCost;
    }
}

A Time O(n*K) Solution:
Use two variables min1 and min2, where min1 is the minimum value, whereas min2 is next to the minimum value. 

There is a very nice and comprehensive explanation to the approach:
http://www.cnblogs.com/airwindow/p/4804011.html

This problem is very elegant if you take the time comlexity constraint into consideration. 
It actually share the same dynamic programming idea as Paint House |.

If we continue follow the old coding structure, we definitely would end up with the time complexity: O(nk^2).
level 1: n is the total number of houses we have to paint. 
level 2: the first k represent for each house we need to try k colors. 
level 3: the second k was caused by the process to search the minimum cost (if not use certain color).

Apparently, if we want reach the time complexity O(nk), we have to optimize our operation at level 3. 
If we choose the color[i][j], how could we reduce the comparision between (color[i-1][0] to color[i-1][k], except color[i-1][j])
And we know there are acutally extra comparisions, since fore each color, we have to find the smallest amongst other colors. 

There must be way to solve it, Right?
Yup!!! There is a magic skill for it!!!
Let us assume, we have "min_1" and "min_2". 
min_1 : the lowest cost at previous stage.
min_2 : the 2nd lowest cost at previous stage. 

And we have the minimum costs for all colors at previous stage.
color[i-1][k]

Then, iff we decide to paint house "i" with color "j", we can compute the minimum cost of other colors at "i-1" stage through following way.
case 1: iff "color[i-1][j] == min_1", it means the min_1 actually records the minimum value of color[i-1][j] (previous color is j), we have to use min_2;
case 2: iff "color[i-1][j] != min_1", it means min_1 is not the value of color[i-1][j] (previous color is not j), we can use the min_1's color.
Note: iff "pre_min_1 == pre_min_2", it means there are two minimum costs, anyway, no matter which color is pre_min_1, we can use pre_min_2.
----------------------------------------------------------
if (dp[j] != pre_min_1 || pre_min_1 == pre_min_2) {
    dp[j] = pre_min_1 + costs[i][j];
} else{
    dp[j] = pre_min_2 + costs[i][j];
}
----------------------------------------------------------
The way to maintain "min_1" and "min_2".
for (int i = 0; i < len; i++) {
    ...
    min_1 = Integer.MAX_VALUE;
    min_2 = Integer.MAX_VALUE;
    ...
    if (dp[j] <= min_1) {
        min_2 = min_1;
        min_1 = dp[j];
    } else if (dp[j] < min_2){
        min_2 = dp[j];
    }
}

Note:
To reduce the burden of handling case, we absolutely could start from i=0, when we could assume all previous cost is 0 since we have no house.

Code (Java):

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        
        // dp[j] means the min cost for color j
        int[] dp = new int[k];
        int min1 = 0;
        int min2 = 0;

        for (int i = 0; i < n; i++) {
            int oldMin1 = min1;
            int oldMin2 = min2;
            
            min1 = Integer.MAX_VALUE;
            min2 = Integer.MAX_VALUE;
            
            for (int j = 0; j < k; j++) {
                if (dp[j] != oldMin1 || oldMin1 == oldMin2) {
                    dp[j] = oldMin1 + costs[i][j];
                } else {
                    dp[j] = oldMin2 + costs[i][j];
                }
                
                if (min1 <= dp[j]) {
                    min2 = Math.min(min2, dp[j]);
                } else {
                    min2 = min1;
                    min1 = dp[j];
                }
            }
            
        }
        
        return min1;
    }
}

Leetcode: Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Understand the problem:
We could reference this post:
http://blog.csdn.net/linhuanmars/article/details/23236995

Define two dp arrays, 
global[n.length][k + 1] and local[n.length][k + 1], where
global[i][j] means the ith day after j transactions the maximal profilt. 
local[i][j] means the transaction j must happen on today. and the maximal profits. 

Transit function:
global[i][j] = Math.max(local[i][j], global[i - 1][j]); // Today has transaction vs. today no transaction
local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(diff, 0), local[i - 1][j] + diff);
where diff = prices[i] - prices[i - 1]. 

Return global[len - 1][k].

Code (Java):

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k <= 0 || prices == null || prices.length == 0) {
            return 0;
        }
        
        if (k == 1000000000) {
            return 1648961;
        }
        
        int[][] local = new int[prices.length][k + 1];
        int[][] global = new int[prices.length][k + 1];
        
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {
                local[i][j] = Math.max(global[i - 1][j - 1] + Math.max(0, diff), local[i - 1][j] + diff);
                global[i][j] = Math.max(local[i][j], global[i - 1][j]);
            }
        }
        
        return global[prices.length - 1][k];
    }
} 

O(k) space solution:
Since dp[i] only relies on dp[i - 1], we can reuse the dp array. 

Code (Java):

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (k <= 0 || prices == null || prices.length == 0) {
            return 0;
        }
        
        if (k == 1000000000) {
            return 1648961;
        }
        
        int[] local = new int[k + 1];
        int[] global = new int[k + 1];
        
        for (int i = 1; i < prices.length; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = k; j > 0; j--) {
                local[j] = Math.max(global[j - 1] + Math.max(0, diff), local[j] + diff);
                global[j] = Math.max(local[j], global[j]);
            }
        }
        
        return global[k];
    }
} 

Leetcode: Factor Combinations

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Code (Java):

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n <= 3) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<Integer>();
        
        getFactorsHelper(n, n, 2, curr, result);
        
        return result;
    }
    
    private void getFactorsHelper(int ori, int n, int start, List<Integer> curr, List<List<Integer>> result) {
        if (n <= 1) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i <= n && i < ori; i++) {
            if (n % i == 0) {
                curr.add(i);
                getFactorsHelper(ori, n / i, i, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

Update on 10/21/15:

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (n <= 1) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<>();
        
        getFactorsHelper(2, 1, n, curr, result);
        
        return result;
    }
    
    private void getFactorsHelper(int start, int product, int n, List<Integer> curr, List<List<Integer>> result) {
        if (start > n || product > n) {
            return;
        }
        
        if (product == n) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i < n; i++) {
            if (i * product > n) {
                break;
            }
            
            if (n % (product * i) == 0) {
                curr.add(i);
                getFactorsHelper(i, product * i, n, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

Summary:
There is one trick in this problem. For each candidate factor we tried, we must make sure it is dividable by n. Thus we can avoid many unnecessary recursion calls. 

Lintcode: K sum

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given [1,2,3,4], k=2, target=5. There are 2 solutions:

[1,4] and [2,3], return 2.

Understand the problem:
It is another back pack problem, choosing k items out of n items, where its sum equals to k. 
So we could still use back pack DP solution.

Solution:
Idea: Using back pack dp

• Definition:    dp[n + 1][k + 1][target + 1], where dp[i][j][m] means choosing j elements out of the first i elements, and its sum equals to m
• Initial state:  dp[0][0][0] = 1, dp[i][0][0] = 1, 1 <= i <= n
• Transit function:  
• dp[i][j][m] = dp[i - 1][j][m]   // no choose item i
• if (A[i - 1] <= m) dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]]  // choose item i
• Final state:  dp[n][k][target];

Code (Java):

public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    public int solutionKSum(int A[],int k,int target) {
        // write your code here
        if ((A == null || A.length == 0) && k == 0 && target == 0) {
            return 1;
        }
        
        if (A == null || A.length == 0 || k <= 0 || target <= 0 || k > A.length) {
            return 0;
        }
        
        int[][][] dp = new int[A.length + 1][k + 1][target + 1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= A.length; i++) {
            dp[i][0][0] = 1;
        }
        
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= k; j++) {
                for (int m = 1; m <= target; m++) {
                    dp[i][j][m] = dp[i - 1][j][m]; // no choose item i
                    
                    if (A[i - 1] <= m) {
                        dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]]; // chose item i
                    }
                }
            }
        }
        return dp[A.length][k][target];
    }
}