Code Implementation

class Solution:
    def minCostII(self, costs):
        if not costs or not costs[0]:
            return 0
        n, k = len(costs), len(costs[0])
        prev_min = prev_second_min = prev_min_color = -1, -1, -1

        dp = [0] * k
        for c in range(k):
            dp[c] = costs[0][c]
        for i in range(1, n):
            min1 = min2 = float('inf')
            min1_color = -1
            new_dp = [0] * k
            for c in range(k):
                if dp[c] < min1:
                    min2 = min1
                    min1 = dp[c]
                    min1_color = c
                elif dp[c] < min2:
                    min2 = dp[c]
            for c in range(k):
                if c == min1_color:
                    new_dp[c] = costs[i][c] + min2
                else:
                    new_dp[c] = costs[i][c] + min1
            dp = new_dp
        return min(dp)
      

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        if (costs.empty() || costs[0].empty()) return 0;
        int n = costs.size(), k = costs[0].size();
        vector<int> dp = costs[0];
        for (int i = 1; i < n; ++i) {
            int min1 = INT_MAX, min2 = INT_MAX, min1_color = -1;
            for (int c = 0; c < k; ++c) {
                if (dp[c] < min1) {
                    min2 = min1;
                    min1 = dp[c];
                    min1_color = c;
                } else if (dp[c] < min2) {
                    min2 = dp[c];
                }
            }
            vector<int> new_dp(k, 0);
            for (int c = 0; c < k; ++c) {
                if (c == min1_color)
                    new_dp[c] = costs[i][c] + min2;
                else
                    new_dp[c] = costs[i][c] + min1;
            }
            dp = new_dp;
        }
        return *min_element(dp.begin(), dp.end());
    }
};
      

class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) return 0;
        int n = costs.length, k = costs[0].length;
        int[] dp = new int[k];
        for (int c = 0; c < k; ++c) dp[c] = costs[0][c];
        for (int i = 1; i < n; ++i) {
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE, min1Color = -1;
            for (int c = 0; c < k; ++c) {
                if (dp[c] < min1) {
                    min2 = min1;
                    min1 = dp[c];
                    min1Color = c;
                } else if (dp[c] < min2) {
                    min2 = dp[c];
                }
            }
            int[] newDp = new int[k];
            for (int c = 0; c < k; ++c) {
                if (c == min1Color)
                    newDp[c] = costs[i][c] + min2;
                else
                    newDp[c] = costs[i][c] + min1;
            }
            dp = newDp;
        }
        int res = Integer.MAX_VALUE;
        for (int cost : dp) res = Math.min(res, cost);
        return res;
    }
}
      

var minCostII = function(costs) {
    if (!costs || costs.length === 0 || costs[0].length === 0) return 0;
    let n = costs.length, k = costs[0].length;
    let dp = [...costs[0]];
    for (let i = 1; i < n; ++i) {
        let min1 = Infinity, min2 = Infinity, min1Color = -1;
        for (let c = 0; c < k; ++c) {
            if (dp[c] < min1) {
                min2 = min1;
                min1 = dp[c];
                min1Color = c;
            } else if (dp[c] < min2) {
                min2 = dp[c];
            }
        }
        let newDp = new Array(k);
        for (let c = 0; c < k; ++c) {
            if (c === min1Color)
                newDp[c] = costs[i][c] + min2;
            else
                newDp[c] = costs[i][c] + min1;
        }
        dp = newDp;
    }
    return Math.min(...dp);
};
      

Problem Description

The "Paint House II" problem asks you to paint a row of n houses, each with one of k colors. The cost of painting house i with color j is given by costs[i][j]. The rule is that no two adjacent houses can have the same color. Your task is to find the minimum total cost to paint all the houses under this constraint. If it's not possible, return 0.

• Each house must be painted with exactly one color.
• No two adjacent houses can have the same color.
• The input is a 2D array costs where costs[i][j] is the cost of painting house i with color j.
• You must return the minimum total painting cost.

Thought Process

At first glance, you might consider trying every possible color for every house, ensuring that no two neighbors share the same color. This brute-force approach would quickly become impractical as the number of houses and colors increases, since the number of combinations grows exponentially.

We need to optimize. Notice that the problem has overlapping subproblems and optimal substructure, making it a good candidate for dynamic programming. The main challenge is efficiently determining, for each house and color, the minimum cost of painting up to that house without violating the adjacency rule.

The key insight is that for each house, if you know the minimum and second minimum costs of painting the previous house, you can quickly compute the minimum cost for the current house without checking all color combinations each time.

Solution Approach

• Step 1: Initialize DP Array
  • We use a 1D array dp where dp[c] is the minimum total cost to paint up to the current house with color c.
  • For the first house, dp[c] = costs[0][c] for all colors c.
• Step 2: Iterate Through Houses
  • For each subsequent house, we need to choose, for each color, the minimum cost of painting the previous house with a different color.
  • To do this efficiently, track the smallest (min1) and second smallest (min2) values in the dp array, along with the color index (min1_color) that achieved min1.
• Step 3: Update DP Array
  • For each color c in the current house:
  • If c is the same as min1_color, use min2 (since we can't use the same color as the previous house).
  • Otherwise, use min1.
  • Update new_dp[c] = costs[i][c] + (min2 or min1) accordingly.
  • After processing all colors, set dp = new_dp for the next iteration.
• Step 4: Final Answer
  • After processing all houses, the answer is the minimum value in dp.

This approach reduces the time complexity from O(nk²) to O(nk), which is efficient enough for large inputs.

Example Walkthrough

Let's consider a small example:

    costs = [
      [1, 5, 3],
      [2, 9, 4]
    ]
  

• First house: costs are [1, 5, 3]. So dp = [1, 5, 3].
• Find min1=1 (color 0), min2=3 (color 2).
• Second house:
  • Color 0: previous min1 was color 0, so use min2: 2 + 3 = 5
  • Color 1: previous min1 was not color 1, so use min1: 9 + 1 = 10
  • Color 2: previous min1 was not color 2, so use min1: 4 + 1 = 5
• Now dp = [5, 10, 5]. The answer is min(dp) = 5.

So, the minimum cost to paint both houses without adjacent colors matching is 5.

Time and Space Complexity

• Brute-force Approach:
  • For each house, try every color, and for each, try every valid color for the next house: O(k^n).
  • This is infeasible for large n or k.
• Optimized DP Approach:
  • For each of n houses, we process k colors, and for each, find min1 and min2 in O(k), so total is O(nk).
  • Space complexity is O(k) since we only store the current dp array.

Summary

The Paint House II problem is a classic dynamic programming challenge. By recognizing the need to efficiently select the minimum cost for each color without repeating the color of the previous house, we leverage the idea of tracking the smallest and second smallest costs at each step. This insight reduces the time complexity dramatically, making the solution both elegant and practical even for large input sizes.