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

⌘K

Tutor

Get Premium

Dynamic Programming

Paint House II

hard

DESCRIPTION (credit Leetcode.com)

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

costs[i][j] = cost to paint house i with color j

There's one constraint: no two adjacent houses can share the same color.

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

Follow-up: Can you solve it in O(n × k) time instead of the naive O(n × k²) approach?

Example 1

Input:

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

Output:

Explanation:

Paint house 0 with color 0 (cost = 1)
Paint house 1 with color 2 (cost = 4)
Total = 1 + 4 = 5

Example 2

Input:

costs = [[1, 3], [2, 4]]

Output:

Explanation: Paint house 0 with color 0 (cost = 1), house 1 with color 1 (cost = 4). Total = 5.

Explanation

This problem is a generalization of Paint House where instead of 3 colors, we now have k colors. The naive approach would be O(n × k²), but we can optimize it to O(n × k) using a clever observation.

The Naive Approach

Following the same logic as Paint House, we could define:

dp[i][j] = minimum cost to paint houses 0 to i, where house i is painted with color j

The recurrence would be:

dp[i][j] = costs[i][j] + min(dp[i-1][m] for all m != j)

This requires O(k) time to find the minimum for each of k colors, resulting in O(n × k²) time complexity.

The Key Optimization

Here's the crucial insight: when computing dp[i][j], we need the minimum of all dp[i-1][m] where m != j.

For most colors, this minimum is simply the overall minimum from the previous row. The only exception is when j equals the index of that minimum - in that case, we use the second minimum.

So we only need to track:

min1: The smallest value in the previous row
min2: The second smallest value in the previous row
min1Idx: The index of min1

This reduces our lookup from O(k) to O(1)!

Walkthrough Example

Let's trace through costs = [[1, 5, 3], [2, 9, 4], [8, 1, 6], [4, 2, 3]]:

House 0 (Base Case):

prev = [1, 5, 3]
min1 = 1 (at index 0), min2 = 3

House 1: For each color j:

j=0: Can't use min1 (same index), so use min2: 2 + 3 = 5
j=1: Use min1: 9 + 1 = 10
j=2: Use min1: 4 + 1 = 5
prev = [5, 10, 5]
New min1 = 5 (at index 0), min2 = 5

House 2:

j=0: Can't use min1: 8 + 5 = 13
j=1: Use min1: 1 + 5 = 6
j=2: Use min1: 6 + 5 = 11
prev = [13, 6, 11]
New min1 = 6 (at index 1), min2 = 11

House 3:

j=0: Use min1: 4 + 6 = 10
j=1: Can't use min1: 2 + 11 = 13
j=2: Use min1: 3 + 6 = 9
prev = [10, 13, 9]

Answer: min(10, 13, 9) = 9 ✓

The min1/min2 optimization is a powerful pattern! It appears in many DP problems where you need "minimum excluding current index" efficiently.

Visualization


def min_cost_ii(costs):
    if not costs:
        return 0
    
    n, k = len(costs), len(costs[0])
    prev = costs[0][:]
    
    for i in range(1, n):
        min1, min2, min1_idx = float('inf'), float('inf'), -1
        for j in range(k):
            if prev[j] < min1:
                min2, min1, min1_idx = min1, prev[j], j
            elif prev[j] < min2:
                min2 = prev[j]
        
        curr = [0] * k
        for j in range(k):
            if j == min1_idx:
                curr[j] = costs[i][j] + min2
            else:
                curr[j] = costs[i][j] + min1
        prev = curr
    
    return min(prev)

paint house II

0 / 20

O(nk) solution using min tracking

Solution

The optimized solution maintains only the previous row's values and tracks min1, min2, and min1Idx. For each new cell, we can determine the minimum from the previous row in O(1) time.

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n × k) where n is the number of houses and k is the number of colors. We iterate through each house once, and for each house we do O(k) work to find min1/min2 and compute the new row.

Space Complexity: O(k) We only store the previous row's values (length k) instead of the full n × k table.

Why Not O(1) Space?

Unlike Paint House with 3 colors where we used just 3 variables, here we need to store all k values from the previous row. We can't optimize to O(1) because we need access to all k previous values to compute the new k values.

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

The Naive Approach

The Key Optimization

Walkthrough Example

Visualization

Solution

Why Not O(1) Space?

Dynamic Programming

Paint House II

DESCRIPTION (credit Leetcode.com)

Explanation

The Naive Approach

The Key Optimization

Walkthrough Example

Visualization

Solution

Test Your Knowledge

Complexity Analysis

Why Not O(1) Space?

Purchase Premium to Access

This article is only available to Premium users.

The best mocks on the market.

Questions

Learn

Links

Legal

Contact