265. 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?

Solution:

This problem is similar to Paint House.

The difference is that for each house, we need to compare k previous minimum costs.

To optimize this, we find that when we check the costs in i-1th  house, we do not need check all k values.

Instead, we only need the two smallest values min and secondmin.

If we find the current color is the same with the one with min, we add secondmin.

Otherwise we can safely add min.

Thus, we can achieve O(n) time complexity and O(1) space complexity.



Code:

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        if (costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        int prevMin = 0;
        int prevSecond = 0;
        int prevIndex = 0;
        for (int i = 0; i < costs.length; i++) {
            int currMin = Integer.MAX_VALUE;
            int currSecond = Integer.MAX_VALUE;
            int currIndex = -1;
            for (int j = 0; j < costs[0].length; j++) {
                costs[i][j] = costs[i][j] + (j == prevIndex ? prevSecond : prevMin);
                if (costs[i][j] < currMin) {
                    currSecond = currMin;
                    currMin = costs[i][j];
                    currIndex = j;
                }
                else if (costs[i][j] < currSecond) {
                    currSecond = costs[i][j];
                }
            }
            prevMin = currMin;
            prevSecond = currSecond;
            prevIndex = currIndex;
        }
        return prevMin;
    }
}