265. Paint House II (https://leetcode.com/problems/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 cert…

265. Paint House II (#1 Array + DP).java

// Array + DP solution: keep the min & second min of last row
// Time: O(nk), 2ms
// Space: O(1) by overwriting the input, 40.9mb
class Solution {
    public int minCostII(int[][] costs) {
        // Corner case
        if(costs == null || costs.length == 0) return 0;
        
        // Find the min and second min in the first row
        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE, minIndex = -1;
        for(int i = 0; i < costs[0].length; i++) {
            if(costs[0][i] < min) {
                secondMin = min;
                min = costs[0][i];
                minIndex = i;
            } else if(costs[0][i] >= min && costs[0][i] < secondMin) {
                secondMin = costs[0][i];
            }
        }
        
        // Iterate through the costs matrix
        for(int i = 1; i < costs.length; i++) {
            int currMin = Integer.MAX_VALUE, currSecMin = Integer.MAX_VALUE, currMinIndex = -1;
            
            for(int j = 0; j < costs[i].length; j++) {
                // Update the current row with min & secondMin of last row
                if(j == minIndex) {
                    costs[i][j] += secondMin;
                } else {
                    costs[i][j] += min;
                }
                
                // Find the min and second min of current row
                if(costs[i][j] < currMin) {
                    currSecMin = currMin;
                    currMin = costs[i][j];
                    currMinIndex = j;
                } else if(costs[i][j] >= currMin && costs[i][j] < currSecMin) {
                    currSecMin = costs[i][j];
                }
            }
            
            // Update min & secondMin for next row
            min = currMin;
            secondMin = currSecMin;
            minIndex = currMinIndex;
        }
        
        return min;
    }
}

265. Paint House II (#1.1 Array + DP).java

// Array + DP solution: keep the min & second min of last row
// Time: O(nk), 2ms
// Space: O(1) (not overwriting the input), 40.6mb
class Solution {
    public int minCostII(int[][] costs) {
        // Corner case
        if(costs == null || costs.length == 0) return 0;
        
        // Find the min and second min in the first row
        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE, minIndex = -1;
        for(int i = 0; i < costs[0].length; i++) {
            if(costs[0][i] < min) {
                secondMin = min;
                min = costs[0][i];
                minIndex = i;
            } else if(costs[0][i] >= min && costs[0][i] < secondMin) {
                secondMin = costs[0][i];
            }
        }
        
        // Iterate through the costs matrix
        for(int i = 1; i < costs.length; i++) {
            int currMin = Integer.MAX_VALUE, currSecMin = Integer.MAX_VALUE, currMinIndex = -1;
            
            for(int j = 0; j < costs[i].length; j++) {
                // Calculate the current row with min & secondMin of last row
                int curr = costs[i][j];
                if(j == minIndex) {
                    curr += secondMin;
                } else {
                    curr += min;
                }
                
                // Find the min and second min of current row
                if(curr < currMin) {
                    currSecMin = currMin;
                    currMin = curr;
                    currMinIndex = j;
                } else if(curr >= currMin && curr < currSecMin) {
                    currSecMin = curr;
                }
            }
            
            // Update min & secondMin for next row
            min = currMin;
            secondMin = currSecMin;
            minIndex = currMinIndex;
        }
        
        return min;
    }
}