Problem Explanation

We are given a row of n houses, where each house can be painted with one of the k colors. The cost of painting each house with a certain color, is represented by a n * k cost matrix. We need to paint all the houses such that no two adjacent houses have the same color. The goal is to find the minimum cost to paint all houses.

Walk Through

Consider an example where we have three houses and three different colors. The costs are represented in a cost matrix as shown :

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

This means,

House 0 will cost us 1 when painted color 0, 5 when painted color 1 and 3 when painted color 2.

Similarly, for the rest of the houses we know the costs for painting them with the respective colors.

The optimal solution in this case would be painting the first house with color 0, the second house with color 2 and the third house with color 1. Thus, we get a minimum cost of 1 + 4 + 2 = 7.

This problem can be solved by using dynamic programming by taking into account the two minimum costs previously calculated, and the colour used for achieving the minimum cost.

Now, let's go over the code implementation in various languages.

Python Solution

1
2python
3class Solution(object):
4    def minCostII(self, costs):
5        if costs is None or len(costs) == 0: return 0
6        min1 = min2 = 0 # minimum cost and second minimum cost
7        idx1 = -1 # index used to trace the color resulting to min1
8        for cost in costs:
9            curr_min1 = curr_min2 = float("inf")
10            curr_idx1 = -1
11            for i in range(len(cost)):
12                # if the color is the same as previous color resulting in min1 cost
13                if i == idx1:
14                    cost[i] += min2 
15                else:
16                    cost[i] += min1
17                # update the cost
18                if cost[i] < curr_min1: 
19                    curr_min2 = curr_min1 
20                    curr_min1 = cost[i]
21                    curr_idx1 = i
22                elif cost[i] < curr_min2:
23                    curr_min2 = cost[i]
24            min1 = curr_min1 
25            min2 = curr_min2
26            idx1 = curr_idx1
27        return min1

Javascript Solution

1
2javascript
3var minCost = function(costs) {
4    if (!costs.length) return 0
5    const dp = [costs[0]]
6    for (let i = 1; i < costs.length; i++) {
7        dp[i] = []
8        for (let j = 0; j < costs[i].length; j++) {
9            dp[i][j] = costs[i][j] + Math.min(...dp[i-1].slice(0, j), ...dp[i-1].slice(j+1))
10        }
11    }
12    return Math.min(...dp[dp.length - 1])
13};

Java Solution

1
2java
3class Solution {
4    public int minCostII(int[][] costs) {
5        if (costs == null || costs.length == 0) {
6            return 0;
7        }
8
9        int n = costs.length, k = costs[0].length;
10        int min1 = 0, min2 = 0, min_index = -1; // min_index is used to record the color j.
11
12        for (int i = 0; i < n; i++) {
13            int cur_min1 = Integer.MAX_VALUE, cur_min2 = Integer.MAX_VALUE, cur_index = 0;
14            for (int j = 0; j < k; j++) {
15                // calculate the cost = "the cost of the house and color" + "the min cost of previous house"
16                int cost = costs[i][j] + (j == min_index ? min2 : min1);
17                // update cur_min1, cur_min2
18                if (cost < cur_min1) { 
19                    cur_min2 = cur_min1;
20                    cur_min1 = cost;
21                    cur_index = j;
22                } else if (cost < cur_min2) {
23                    cur_min2 = cost;
24                }
25            }
26            min1 = cur_min1; 
27            min2 = cur_min2; 
28            min_index = cur_index;
29        }
30        return min1;
31    }
32}

C# Solution

1
2csharp
3public class Solution {
4    public int MinCostII(int[][] costs) {
5        if (costs.Length == 0)
6            return 0;
7            
8        int n = costs.Length, k = costs[0].Length;
9        int min1 = -1, min2 = -1;
10        for (int i = 0; i < n; i++)
11            for (int j = 0; j < k; j++)
12                if (j != min1)
13                {
14                    // j is different to min1, so it's okay
15                    costs[i][j] += min1 < 0 ? 0 : costs[i - 1][min1];
16                }
17                else
18                {
19                    // j is equal to min1, so need to add costs[i - 1][min2]
20                    costs[i][j] += min2 < 0 ? 0 : costs[i - 1][min2];
21                }
22        
23        min1 = min2 = -1;
24        for (int j = 0; jk; j++) {
25            if (min1 < 0 || costs[n - 1][j] <= costs[n - 1][min1]) {
26                min2 = min1; 
27                min1 = j;
28            } else if (min2 < 0 || costs[n - 1][j] <= costs[n - 1][min2])
29                min2 = j;
30        }
31        return costs[n - 1][min1];
32    }
33}
34

C++ Solution

1
2c++
3class Solution {
4public:
5    int minCostII(vector<vector<int>>& costs) {
6        if(costs.empty()) return 0;
7        vector<int> DP(costs[0].size(), 0);
8        int k = costs[0].size();
9        
10        for(int i=0; i<costs.size();i++){
11            vector<int> new_dp(k, INT_MAX);
12            for(int color=0;color<k;color++){
13                for(int prev_color = 0; prev_color<k;prev_color++){
14                    if(color == prev_color) continue;
15                    new_dp[color] = min(new_dp[color], DP[prev_color] + costs[i][color]);
16                }
17            }
18            DP = new_dp;
19        }
20        
21        return *min_element(DP.begin(), DP.end());
22    }
23};

In the above solutions, 'min_cost_' variable captures the minimum cost for painting the house considering the previous house's colors and cost. The second variable 'min2' captures the second minimal cost when the color of the house is the same as its previous house. We then have a variable 'idx1' to save the color index which brings the minimum cost.

For each color 'i', we check if the color is the same as the color resulting in the 'min1' cost. If it is, we add the second minimum cost 'min2' to the current house's cost. If not, we add the 'min1' cost to the current house's cost.

Finally, we update our 'min1', 'min2', and 'idx1' for the next house use. The implementation focuses on finding a way to bypass the color that brings the minimum cost when we know that color cannot be used on the next house (due to no two adjacent houses can have the same color rule).

Complexity Analysis

The space complexity for this solution is O(1), which means the space use is constant because no additional space is used.

The time complexity is O(n * k), where 'n' is the number of houses and 'k' is the number of colors. This time complexity comes from two nested loops: the outer one loops over the houses and the inner one loops over the colors.

These solutions are efficient and solve the problem in a systematic way using Dynamic Programming concept. Dynamic Programming helps to simplify a complex problem by breaking it down into simpler sub-problems in a recursive manner.