LeetCode - Paint House II

PaintHouseII.java

// O(m*k*k)
public int minCostII(int[][] costs) {
    // Write your code here
    if(costs.length == 0 || costs[0].length == 0) return 0;
    int m = costs.length, n = costs[0].length;
    for(int i=1; i<m; i++){
        for(int j=0; j<n; j++){
            int min = Integer.MAX_VALUE;
            for(int k=0; k<n; k++){
                if(k == j) continue;
                int localMin = costs[i-1][k] + costs[i][j];
                min = Math.min(localMin, min);
            }
            costs[i][j] = min;
        }
    }
    
    int res = Integer.MAX_VALUE;
    for(int j=0; j<n; j++){
        res = Math.min(costs[m-1][j], res);
    }
    return res;
}

// O(m * k)
public int minCostII(int[][] costs) {
    // Write your code here
    if(costs.length == 0 || costs[0].length == 0) return 0;
    
    int m = costs.length, n = costs[0].length;
    int min1 = -1, min2 = -1;
    
    for(int i=0; i<m; i++){
        int last1 = min1, last2 = min2;
        min1 = -1; min2 = -1;
        
        for(int j=0; j<n; j++){
            if(j != last1){
                costs[i][j] += last1 < 0 ? 0 : costs[i-1][last1];
            } else {
                costs[i][j] += last2 < 0 ? 0 : costs[i-1][last2];
            }
            
            // update the min1 and min2
            if(min1 < 0 || costs[i][j] < costs[i][min1]){
                min2 = min1;
                min1 = j;
            } else if(min2 < 0 || costs[i][j] < costs[i][min2]) {
                min2 = j;
            }
        }
    }
   
    return costs[m-1][min1];
}