265. Paint House II
Problem Description
In this problem, we are given n
houses in a row and each house can be painted with one of k
colors. The costs of painting each house with a certain color are provided in a two-dimensional array (matrix) called costs
. The costs
matrix has n
rows (representing each house) and k
columns (representing each color's cost for that house). For example, costs[i][j]
gives the cost of painting the i
-th house with the j
-th color. The main objective is to determine the minimum total cost to paint all the houses while ensuring that no two adjacent houses are painted the same color.
Intuition
The intuition behind solving this problem lies in breaking it down into a sequence of decisions, where for each house we choose a color. However, we must make this decision considering the cost of the current house as well as ensuring that it doesn't have the same color as the adjacent house. We approach the solution dynamically, by building up the answer as we go along.
-
We initialize our answer with the cost of painting the first house, which is simply the costs of painting that house with each color (the first row of our
costs
matrix). -
Then for each subsequent house, we update the cost of painting it with each color by adding the minimum cost of painting the previous house with a different color. This ensures we meet the requirement that no two adjacent houses share the same color.
-
To efficiently perform this operation, we maintain a temporary array
g
which stores the new costs calculated for painting the current house. For each colorj
, we find the minimum cost from the arrayf
(which stores the costs for the previous house) excluding thej
-th color. -
We then add the current cost (
costs[i][j]
) to this minimum cost and store it ing[j]
. At the end of each iteration, we assigng
tof
, so thatf
now represents the costs of painting up to the current house. -
After processing all houses,
f
will contain the total costs of painting all houses where the last house is painted with each of thek
colors. Our answer is the minimum of these costs.
Through dynamic programming, the code optimizes the painting cost by cleverly tracking and updating the costs while satisfying the problem's constraints.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution follows a dynamic programming pattern, which is often used to break down a complex problem into smaller, easier-to-manage subproblems.
-
We start with an initialization where we assign the costs of painting the first house with the
k
different colors directly to our first version of thef
array. This sets up our base case for the dynamic programming solution.f = costs[0][:]
-
We then iterate over each of the remaining houses
(i)
from the second house (1
) to the last house(n - 1)
. For each house, we need to calculate the new costs of painting it with each possible color(j)
.for i in range(1, n): g = costs[i][:] ...
-
For each color
(j)
, we determine the minimum cost of painting the previous house with any color other thanj
. This is done to ensure that the same color is not used for adjacent houses.To find that minimum, we iterate through all the possible colors (
h
), ignoring the current colorj
. This inner loop effectively finds the lowest cost to paint the previous house with a different color.for j in range(k): t = min(f[h] for h in range(k) if h != j) ...
-
The found minimum cost
t
is then added to the current cost of painting the housei
with colorj
(costs[i][j]
). The result is the total cost to get to housei
, having it painted with colorj
, and is stored ing[j]
.g[j] += t
-
Once all colors for the current house have been evaluated, we update the
f
array to be our newly calculatedg
.f = g
-
After we have finished iterating through all the houses, the
f
array holds the minimum cost to paint all the houses up until the last, with the index representing the color used for the last house. -
The final step is to find the minimum value within the
f
array since this represents the lowest possible cost for painting all the houses while following the rules. This is the value that is returned as the answer.return min(f)
The pattern used here leverages dynamic programming's key principle: solve the problem for a small section (the first house, in this case) and then build upon that solution incrementally, tackling a new subproblem in each iteration (each subsequent house). While the problem itself has potentially a very large number of combinations, dynamic programming allows us to consider only the relevant ones and efficiently find the solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach using the dynamic programming pattern described.
- Imagine we have
n = 3
houses andk = 3
colors. - The
costs
matrix provided to us is:[[1,5,3], [2,9,4], [3,1,5]]
. This means:- To paint house 0, it costs 1 for color 0, 5 for color 1, and 3 for color 2.
- To paint house 1, it costs 2 for color 0, 9 for color 1, and 4 for color 2.
- To paint house 2, it costs 3 for color 0, 1 for color 1, and 5 for color 2.
Applying the approach:
-
We initialize
f
with the costs to paint the first house, sof
will be[1, 5, 3]
. -
We move on to the second house and create a new temporary array
g
, which initially contains the costs for the second house:g = costs[1][:]
org = [2, 9, 4]
. -
Next, we find the minimum cost to paint the previous house with a color different from the color we want to use for the current house.
For
g[0]
(house 1, color 0), we look for the minimum cost of painting house 0 with colors 1 or 2. The minimum of[5, 3]
is3
, sog[0] += 3
, resulting ing[0] = 5
.For
g[1]
(house 1, color 1), we look for the minimum cost of painting house 0 with colors 0 or 2. The minimum of[1, 3]
is1
, sog[1] += 1
, resulting ing[1] = 10
.For
g[2]
(house 1, color 2), we look for the minimum cost of painting house 0 with colors 0 or 1. The minimum of[1, 5]
is1
, sog[2] += 1
, resulting ing[2] = 5
. -
Now
g
is updated to[5, 10, 5]
and we updatef
withg
. So nowf = g
. -
We repeat the process for the third house.
We start with
g = costs[2][:]
org = [3, 1, 5]
.For
g[0]
, we look for the minimum cost off[1]
orf[2]
, which is the minimum of[10, 5]
and that is5
, sog[0] += 5
resulting ing[0] = 8
.For
g[1]
, we look for the minimum cost off[0]
orf[2]
, which is the minimum of[5, 5]
and that is5
, sog[1] += 5
resulting ing[1] = 6
.For
g[2]
, we look for the minimum cost off[0]
orf[1]
, which is the minimum of[5, 10]
and that is5
, sog[2] += 5
resulting ing[2] = 10
. -
Updated
g
for the last house is[8, 6, 10]
, this becomes newf
, sof = [8, 6, 10]
. -
Finally, we find the minimum cost to paint all houses by taking the minimum of
f
, which is6
. Therefore, the minimum cost to paint all the houses while ensuring no two adjacent houses have the same color is6
.
Solution Implementation
1class Solution:
2 def minCostII(self, costs: List[List[int]]) -> int:
3 # Get the number of houses (n) and the number of colors (k)
4 num_houses, num_colors = len(costs), len(costs[0])
5
6 # Initialize the previous row with the costs of the first house
7 prev_row_costs = costs[0][:]
8
9 # Iterate through the rest of the houses
10 for house_index in range(1, num_houses):
11 # Initialize costs for the current row
12 curr_row_costs = costs[house_index][:]
13
14 # Iterate through each color for the current house
15 for color_index in range(num_colors):
16 # Find the minimum cost for the previous house, excluding the current color index
17 min_cost_except_current = min(
18 prev_row_costs[color] for color in range(num_colors) if color != color_index
19 )
20
21 # Add the minimum cost found to the current color cost
22 curr_row_costs[color_index] += min_cost_except_current
23
24 # Update the previous row costs for the next iteration
25 prev_row_costs = curr_row_costs
26
27 # Return the minimum cost for painting all houses with the last row of costs
28 return min(prev_row_costs)
29
1class Solution {
2 public int minCostII(int[][] costs) {
3 int numHouses = costs.length; // Number of houses is the length of the costs array
4 int numColors = costs[0].length; // Number of colors available for painting is the length of the first item in costs array
5 int[] previousCosts = costs[0].clone(); // Clone the first house's cost as the starting point
6
7 // Iterate over each house starting from the second house
8 for (int houseIndex = 1; houseIndex < numHouses; ++houseIndex) {
9 int[] currentCosts = costs[houseIndex].clone(); // Clone the current house's costs
10 // Iterate through each color for the current house
11 for (int colorIndex = 0; colorIndex < numColors; ++colorIndex) {
12 int minCost = Integer.MAX_VALUE;
13 // Find the minimum cost of painting the previous house with a different color
14 for (int prevColorIndex = 0; prevColorIndex < numColors; ++prevColorIndex) {
15 // Skip if it is the same color as the current one
16 if (prevColorIndex != colorIndex) {
17 minCost = Math.min(minCost, previousCosts[prevColorIndex]);
18 }
19 }
20 // Add the minimum found cost to paint the previous house to the current house's color cost
21 currentCosts[colorIndex] += minCost;
22 }
23 // Update previousCosts to currentCosts for the next iteration
24 previousCosts = currentCosts;
25 }
26
27 // Find and return the minimum cost from the last house's painting cost array
28 return Arrays.stream(previousCosts).min().getAsInt();
29 }
30}
31
1#include <vector>
2#include <algorithm>
3#include <climits>
4using namespace std;
5
6class Solution {
7public:
8 int minCostII(vector<vector<int>>& costs) {
9 int numHouses = costs.size(); // Number of houses
10 int numColors = costs[0].size(); // Number of colors
11
12 // Initialize the first row of the DP table with costs of painting the first house
13 vector<int> dpTable = costs[0];
14
15 // Loop over each house starting from the second
16 for (int houseIndex = 1; houseIndex < numHouses; ++houseIndex) {
17 // Temporary vector to hold the new costs for the current house
18 vector<int> newCosts = costs[houseIndex];
19
20 // Loop over each color for the current house
21 for (int currentColor = 0; currentColor < numColors; ++currentColor) {
22 int minCost = INT_MAX; // Initialize minCost to the largest possible value
23
24 // Find the minimum cost to paint the previous house with a color different from currentColor
25 for (int previousColor = 0; previousColor < numColors; ++previousColor) {
26 if (previousColor != currentColor) {
27 minCost = min(minCost, dpTable[previousColor]);
28 }
29 }
30
31 // Add the minimum cost found to paint the previous house with the cost to paint the current house
32 newCosts[currentColor] += minCost;
33 }
34
35 // Move the values in newCosts to dpTable for the next iteration
36 dpTable = move(newCosts);
37 }
38
39 // Return the minimum element in dpTable (which now contains the minimum cost to paint all houses)
40 return *min_element(dpTable.begin(), dpTable.end());
41 }
42};
43
1function minCostII(costs: number[][]): number {
2 const numHouses: number = costs.length; // Number of houses
3 const numColors: number = costs[0].length; // Number of colors
4
5 // Initialize the first row of the DP table with costs of painting the first house
6 let dpTable: number[] = [...costs[0]];
7
8 // Loop over each house starting from the second
9 for (let houseIndex = 1; houseIndex < numHouses; houseIndex++) {
10 // Temporary array to hold the new costs for the current house
11 const newCosts: number[] = [...costs[houseIndex]];
12
13 // Loop over each color for the current house
14 for (let currentColor = 0; currentColor < numColors; currentColor++) {
15 let minCost: number = Number.MAX_SAFE_INTEGER; // Initialize minCost to the largest possible safe integer value
16
17 // Find the minimum cost to paint the previous house with a color different from currentColor
18 for (let previousColor = 0; previousColor < numColors; previousColor++) {
19 if (previousColor !== currentColor) {
20 minCost = Math.min(minCost, dpTable[previousColor]);
21 }
22 }
23
24 // Add the minimum cost found to paint the previous house with the cost to paint the current house
25 newCosts[currentColor] += minCost;
26 }
27
28 // Move the values in newCosts to dpTable for the next iteration
29 dpTable = newCosts;
30 }
31
32 // Return the minimum element in dpTable (which now contains the minimum cost to paint all houses)
33 return Math.min(...dpTable);
34}
35
Time and Space Complexity
Time Complexity:
The given code iterates over n
rows, and for each row, it iterates over k
colors to calculate the minimum cost. Inside the inner loop, there is another loop that again iterates over k
colors to find the minimum cost of painting the previous house with a different color, avoiding the current one.
Therefore, for each of the n
rows, the code performs O(k)
operations for each color, and within that, it performs another O(k)
to find the minimum. This results in a time complexity of O(n * k * k)
.
Space Complexity:
The space complexity of the code is determined by the additional space used for the f
and g
arrays, both of size k
. No other significant space is being used that scales with the input size. Thus the space complexity is O(k)
.
Learn more about how to find time and space complexity quickly using problem constraints.
A heap is a ...?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!