Leetcode 265. Paint House II
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.