Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Dynamic Programming

Paint House

medium

DESCRIPTION (credit Leetcode.com)

You have a row of n houses along a street, and each house needs to be painted with one of three colors: Red, Blue, or Green. The painting costs vary for each house and color combination, given in a 2D array costs where:

costs[i][0] = cost to paint house i Red
costs[i][1] = cost to paint house i Blue
costs[i][2] = cost to paint house i Green

There's one constraint: to keep the neighborhood visually appealing, no two adjacent houses can share the same color.

Write a function to return the minimum total cost to paint all houses.

Example 1

Input:

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

Output:

Explanation:

Paint house 0 Blue (cost = 2)
Paint house 1 Green (cost = 5)
Paint house 2 Blue (cost = 3)
Total = 2 + 5 + 3 = 10

Example 2

Input:

costs = [[7, 6, 2]]

Output:

Explanation: With a single house, pick the cheapest color (Green at cost 2).

Example 3

Input:

costs = [[3, 5, 3], [6, 17, 6], [7, 13, 18], [9, 10, 18]]

Output:

Explanation

This problem is a classic example of dynamic programming with state tracking. The key insight is that the minimum cost to paint house i depends on which color we used for house i - 1.

Defining the State

Let's define our DP state as follows:

dp[i][0] = minimum cost to paint houses 0 to i, where house i is painted Red
dp[i][1] = minimum cost to paint houses 0 to i, where house i is painted Blue
dp[i][2] = minimum cost to paint houses 0 to i, where house i is painted Green

Our goal is to find the minimum of dp[n-1][0], dp[n-1][1], and dp[n-1][2].

The Recurrence Relation

Since adjacent houses cannot have the same color, if we want to paint house i with a certain color, we must have painted house i - 1 with one of the other two colors.

For example, if we want to paint house i Red:

House i - 1 must be either Blue or Green
So dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])

This gives us our recurrence relations:

dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])  # Paint house i Red
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])  # Paint house i Blue
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])  # Paint house i Green

Base Case

For the first house (i = 0), there's no constraint from a previous house, so:

dp[0][0] = costs[0][0]  # Cost to paint house 0 Red
dp[0][1] = costs[0][1]  # Cost to paint house 0 Blue
dp[0][2] = costs[0][2]  # Cost to paint house 0 Green

Walkthrough Example

Let's trace through the example costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]:

House 0 (Base Case):

Red: 17, Blue: 2, Green: 17

House 1:

Red: 16 + min(2, 17) = 16 + 2 = 18
Blue: 16 + min(17, 17) = 16 + 17 = 33
Green: 5 + min(17, 2) = 5 + 2 = 7

House 2:

Red: 14 + min(33, 7) = 14 + 7 = 21
Blue: 3 + min(18, 7) = 3 + 7 = 10
Green: 19 + min(18, 33) = 19 + 18 = 37

Answer: min(21, 10, 37) = 10

The optimal choice is: House 0 → Blue (2), House 1 → Green (5), House 2 → Blue (3) = 10

Visualization


def min_cost(costs):
    if not costs:
        return 0
    
    n = len(costs)
    dp = [[0] * 3 for _ in range(n)]
    
    # Base case: first house
    dp[0][0] = costs[0][0]  # Red
    dp[0][1] = costs[0][1]  # Blue
    dp[0][2] = costs[0][2]  # Green
    
    # Fill DP table
    for i in range(1, n):
        dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
    
    return min(dp[n-1][0], dp[n-1][1], dp[n-1][2])

paint house - 2D DP approach

0 / 11

2D DP table filling - O(n) space

Space Optimization

Notice that to compute dp[i], we only need values from dp[i-1]. This means we don't need to store the entire 2D array - we can just keep track of the previous row's values.

Instead of a 2D array, we can use just 3 variables to track the minimum costs for each color at the previous house. This reduces space from O(n) to O(1).

This space optimization pattern is common in DP problems where the current state only depends on the immediately previous state.

Solution

The space-optimized solution uses only 3 variables (prevRed, prevBlue, prevGreen) instead of a full 2D table. For each house, we calculate the new costs and then update our variables.

Visualization


def min_cost(costs):
    if not costs:
        return 0
    
    prev_red = costs[0][0]
    prev_blue = costs[0][1]
    prev_green = costs[0][2]
    
    for i in range(1, len(costs)):
        curr_red = costs[i][0] + min(prev_blue, prev_green)
        curr_blue = costs[i][1] + min(prev_red, prev_green)
        curr_green = costs[i][2] + min(prev_red, prev_blue)
        
        prev_red = curr_red
        prev_blue = curr_blue
        prev_green = curr_green
    
    return min(prev_red, prev_blue, prev_green)

paint house

0 / 12

Space-optimized solution - O(1) space

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) where n is the number of houses. We iterate through each house exactly once, and at each house we do constant work (comparing 2 values and adding).

Space Complexity: O(1) The space-optimized solution uses only 3 variables instead of a 2D array. The 2D table approach would use O(n) space.

Purchase Premium to Access

This article is only available to Premium users.

Purchase Premium

The best mocks on the market.

Now up to 25% off

Learn More

Reading Progress

On This Page

Explanation

Defining the State

The Recurrence Relation

Base Case

Walkthrough Example

Space Optimization

Solution

Dynamic Programming

Paint House

DESCRIPTION (credit Leetcode.com)

Explanation

Defining the State

The Recurrence Relation

Base Case

Walkthrough Example

Space Optimization

Solution

Test Your Knowledge

Complexity Analysis

Purchase Premium to Access

This article is only available to Premium users.

The best mocks on the market.

Questions

Learn

Links

Legal

Contact