256. Paint House

Problem Description

In this problem, we are given a scenario where we have n houses in a row, and we need to paint each house in such a way that no two adjacent houses have the same color. There are three colors available: red, blue, and green. The cost of painting each house with each color is different and is provided to us in the form of a n x 3 cost matrix - costs.

Each row in the costs matrix corresponds to a house, and each column to a color (where the first column is red, the second is blue, and the third is green). For instance, costs[0][0] represents the cost of painting the first house red, while costs[1][2] represents the cost of painting the second house green.

Our goal is to find the minimum total cost to paint all the houses while making sure that no two adjacent houses are painted the same color.

Intuition

The key to solving this problem lies in understanding that the color choice for each house depends on the color choices made for the previous house. To tackle this, we can use dynamic programming to keep track of the minimum cost up to each house while adhering to the color restriction.

We initialize three variables: a, b, and c, representing the minimum cost of painting the last house with one of the three colors. As we iterate through each house, we update the costs for each color:

a will be updated to the cost of painting the current house red plus the minimum cost of painting the previous house either blue or green (whichever is lesser).
Similarly, b will be updated to the cost of painting the current house blue plus the minimum cost of painting the previous house either red or green.
c will be updated to the cost of painting the current house green plus the minimum cost of painting the previous house either red or blue.

In this way, each choice takes into consideration the previous choices and ensures that no two adjacent houses will have the same color, as we always pick a different color for the current house than the one picked for the previous house (captured in a, b, or c).

Finally, after going through all the houses, we will have the minimum cost accumulated in a, b, and c for ending with each color. The answer will be the minimum of these three values as it represents the least cost of painting all houses while satisfying the constraint.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of the solution follows the dynamic programming strategy since it involves breaking the problem down into subproblems, solving each subproblem just once, and storing their solutions – typically using a memory-based data structure (array, map, etc.).

Here is a step-by-step breakdown of the algorithm used:

Initialization: We start by initializing three variables, a, b, and c to 0. These variables will hold the minimum painting cost for the last painted house for each color (red, blue, and green respectively).
Iterating Over Houses: We then iterate over each house. For each house, we get ca, cb, and cc from the costs matrix, which represent the painting costs for red, blue, and green, respectively.
Updating Costs for Each Color: The core of the solution is updating the cost for each color for the current house. We do this by calculating the minimum cost for painting the current house with a particular color based on the costs of painting the previous house.
- To paint the current house red (ca), we look for the minimum cost between painting the previous house blue or green, which is min(b, c), and add that to the cost of painting the current house red, ca. This updated cost is stored back in a.
- Similarly, to paint the current house blue (cb), we find the minimum cost of a and c and add cb to it, and store this value back in b.
- To paint the current house green (cc), we take the minimum cost from a and b and add cc to it, and store this value in c.
This update ensures that for any house, we choose the color that was not chosen for the last house and had the minimum cost among the remaining colors.

The code snippet for this step is:
```
a, b, c = min(b, c) + ca, min(a, c) + cb, min(a, b) + cc
```
Finding the Minimum Total Cost: After iterating through all the houses, we have three values a, b, and c, each representing the total minimum cost of painting all houses up to this point, with the last house being red, blue, or green respectively. The final step is to return the smallest value among a, b, and c which is min(a, b, c).

This approach uses a constant amount of extra space (for the variables a, b, c) and thus has a space complexity of O(1). The time complexity is O(n) since we iterate through the list of costs once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to illustrate the solution approach in action. Suppose we have the following cost matrix for 3 houses and 3 colors:

costs = [[17, 2, 17],
         [16, 16, 5],
         [14, 3, 19]]

House 1: red = 17, blue = 2, green = 17
House 2: red = 16, blue = 16, green = 5
House 3: red = 14, blue = 3, green = 19

Following the steps of the described solution:

Step 1: Initialization
We initialize a, b, c to 0.

Step 2: Iterating Over Houses
Start with the first house (i = 0):

ca = costs[0][0] = 17
cb = costs[0][1] = 2
cc = costs[0][2] = 17

Step 3: Updating Costs for Each Color Since this is the first house, we simply assign each cost to a, b, and c respectively.

a = 17
b = 2
c = 17

Move to the second house (i = 1):

ca = costs[1][0] = 16
cb = costs[1][1] = 16
cc = costs[1][2] = 5

We now update the costs based on the previous house's costs:

a = min(previous b, c) + current ca = min(2, 17) + 16 = 2 + 16 = 18
b = min(previous a, c) + current cb = min(17, 17) + 16 = 17 + 16 = 33
c = min(previous a, b) + current cc = min(17, 2) + 5 = 2 + 5 = 7

Now, a = 18, b = 33, c = 7.

Move to the third house (i = 2):

ca = costs[2][0] = 14
cb = costs[2][1] = 3
cc = costs[2][2] = 19

Finally, update the costs for the third house:

a = min(previous b, c) + current ca = min(33, 7) + 14 = 7 + 14 = 21
b = min(previous a, c) + current cb = min(18, 7) + 3 = 7 + 3 = 10
c = min(previous a, b) + current cc = min(18, 33) + 19 = 18 + 19 = 37

After considering the third house, a = 21, b = 10, c = 37.

Step 4: Finding the Minimum Total Cost
We look for the smallest value among the final a, b, and c. Which will be the minimum cost to paint all the houses while no two adjacent houses have the same color:

min(a, b, c) = min(21, 10, 37) = 10

Therefore, the minimum total cost to paint all the houses is $10.

This example neatly demonstrates how the dynamic programming approach keeps track of the minimum cost up to each house and updates the cost during each iteration to ensure the final solution adheres to the problem's constraints.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minCost(self, costs: List[List[int]]) -> int:
5        # Initialize the minimum costs for the three colors
6        cost_red = cost_blue = cost_green = 0
7      
8        # Iterate over each house and calculate the minimum cost
9        # of painting each house, not repeating the color of the adjacent house
10        for cost_of_red, cost_of_blue, cost_of_green in costs:
11            # Update the cost of painting each house with red, blue, or green 
12            # by adding the current painting cost to the minimum cost of the 
13            # other two colors from the previous step
14            new_cost_red = min(cost_blue, cost_green) + cost_of_red
15            new_cost_blue = min(cost_red, cost_green) + cost_of_blue
16            new_cost_green = min(cost_red, cost_blue) + cost_of_green
17          
18            # Update the current minimum costs for each color
19            cost_red, cost_blue, cost_green = new_cost_red, new_cost_blue, new_cost_green
20      
21        # Return the minimum cost among the three colors after
22        # completing the calculation for all houses
23        return min(cost_red, cost_blue, cost_green)
24
25# Example usage:
26# solution = Solution()
27# print(solution.minCost([[17,2,17], [16,16,5], [14,3,19]]))
28

1class Solution {
2
3    // Function to calculate the minimum cost of painting houses
4    // with no two adjacent houses having the same color.
5    public int minCost(int[][] costs) {
6        // Initialize variables to store the minimum cost of painting up to the current house
7        int costRed = 0, costGreen = 0, costBlue = 0;
8
9        // Loop through each house and calculate the minimum cost by considering previous house colors
10        for (int[] cost : costs) {
11            // Temporary variables to store previous costs before updating
12            int prevCostRed = costRed, prevCostGreen = costGreen, prevCostBlue = costBlue;
13
14            // Cost of painting current house red is the minimum cost of previous house painted green or blue plus current cost for red
15            costRed = Math.min(prevCostGreen, prevCostBlue) + cost[0];
16          
17            // Cost of painting current house green is the minimum cost of previous house painted red or blue plus current cost for green
18            costGreen = Math.min(prevCostRed, prevCostBlue) + cost[1];
19          
20            // Cost of painting current house blue is the minimum cost of previous house painted red or green plus current cost for blue
21            costBlue = Math.min(prevCostRed, prevCostGreen) + cost[2];
22        }
23
24        // Return the overall minimum cost of painting all houses, which is the minimum of the three colors.
25        return Math.min(costRed, Math.min(costGreen, costBlue));
26    }
27}
28

1class Solution {
2public:
3    // Function to calculate the minimum cost of painting houses.
4    // No two adjacent houses can have the same color.
5    int minCost(vector<vector<int>>& costs) {
6        // Initialize the minimum costs of the last house for 
7        // each color to be zero.
8        int lastRed = 0, lastGreen = 0, lastBlue = 0;
9
10        // Iterate over each house.
11        for (auto& cost : costs) {
12            // Store the previous costs before updating.
13            int prevRed = lastRed, prevGreen = lastGreen, prevBlue = lastBlue;
14          
15            // Update the minimum cost for the current house when painted red.
16            // It is the cost of painting the current house red plus the 
17            // minimum cost of the previous house when it was not red.
18            lastRed = min(prevGreen, prevBlue) + cost[0];
19          
20            // Update the minimum cost for the current house when painted green.
21            // It is the cost of painting the current house green plus the 
22            // minimum cost of the previous house when it was not green.
23            lastGreen = min(prevRed, prevBlue) + cost[1];
24          
25            // Update the minimum cost for the current house when painted blue.
26            // It is the cost of painting the current house blue plus the 
27            // minimum cost of the previous house when it was not blue.
28            lastBlue = min(prevRed, prevGreen) + cost[2];
29        }
30
31        // After considering all houses, return the minimum of the costs
32        // of painting the last house with any of the three colors.
33        return min(lastRed, min(lastGreen, lastBlue));
34    }
35};
36

1/**
2 * Calculates the minimum cost to paint all houses such that no two adjacent houses have the same color.
3 * The cost of painting each house with each color is given in an input array.
4 *
5 * @param {number[][]} paintingCosts - A 2D array where paintingCosts[i][j] represents the cost to paint the i-th house with color j.
6 * @return {number} - The minimum cost to paint all houses.
7 */
8function minCost(paintingCosts: number[][]): number {
9    // Initialize variables to store the cumulative costs of painting houses with three different colors.
10    let costA: number = 0;
11    let costB: number = 0;
12    let costC: number = 0;
13
14    // Iterate over each house's painting cost array.
15    for (let [costColorA, costColorB, costColorC] of paintingCosts) {
16        // Calculate the cumulative cost of painting the current house with each color.
17        // For each color, we choose the minimum of the other two colors' previous cumulative costs.
18        const newCostA: number = Math.min(costB, costC) + costColorA;
19        const newCostB: number = Math.min(costA, costC) + costColorB;
20        const newCostC: number = Math.min(costA, costB) + costColorC;
21
22        // Update the cumulative costs for the next iteration.
23        costA = newCostA;
24        costB = newCostB;
25        costC = newCostC;
26    }
27
28    // The answer is the smallest of the cumulative costs after painting all houses.
29    return Math.min(costA, costB, costC);
30}
31

Time and Space Complexity

The provided code aims to solve a problem where we have a list of costs that represents the cost of painting each house with one of three colors, such that no two adjacent houses have the same color, and we want to find the minimum cost to paint all houses.

Time Complexity

The time complexity of the code is determined by a single loop that iterates over each house exactly once. There are n houses (where n is the length of the costs list), and for each house, it performs a constant amount of work:

Accessing the costs of painting the current house with each of the three colors (ca, cb, cc).
Calculating the new costs for painting the next house with each color by taking the minimum of the previous two not equal colors (the calculation for a, b, c variables).

Since the loop runs n times and does a constant amount of work each time, the time complexity is O(n).

Space Complexity

The space complexity of the code is determined by the additional memory used by the algorithm, not including the input costs themselves. The code only uses a fixed number of variables a, b, and c to keep track of the minimum costs up to the current house for each color, and these are updated in place.

No additional structures that grow with the size of the input are used. Therefore, the space complexity is constant, or O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don’t know