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. Could you solve it in O(nk) runtime?

O(nk) time O(1) space solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length < 1 || costs[0].length < 1) return 0;
        int n = costs.length, k = costs[0].length;
        if (k == 1) 
            return n == 1 ? costs[0][0] : -1;
        int prevFirstMin = 0, prevSecondMin = 0, prevMinColor = -1;
        
        for (int i = 0; i < n; i++) {
            int firstMin = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE, minColor = -1;
            for (int j = 0; j < k; j++) {
                int val = costs[i][j] + (j == prevMinColor ? prevSecondMin : prevFirstMin);
                if (val < firstMin) {
                    minColor = j;
                    secondMin = firstMin;
                    firstMin = val;
                } else if (val < secondMin) {
                    secondMin = val;
                }
            }
            prevFirstMin = firstMin;
            prevSecondMin = secondMin;
            prevMinColor = minColor;
        }
        return prevFirstMin;
    }
}
}