LeetCode 265: Paint House II

Problem Restatement

We are given n houses and k colors.

The painting cost is stored in:

costs[i][j]

which means:

Cost to paint house i using color j.

Adjacent houses cannot use the same color.

We need to return the minimum total painting cost.

Unlike LeetCode 256, the number of colors is not fixed to 3.

The constraints are:

1 <= n <= 100
1 <= k <= 20

The problem asks for the minimum total cost while ensuring neighboring houses have different colors. (leetcode.com)

Input and Output

Example function shape:

def minCostII(costs: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

Possible valid paint choices:

The minimum cost is:

5

Answer:

5

Example 2:

costs = [[1, 3]]

Only one house exists.

Choose the cheapest color.

Answer:

1

First Thought: Standard Dynamic Programming

Define:

dp[i][j]

as:

Minimum cost to paint houses 0..i where house i uses color j.

Transition:

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

This is correct.

But for every house and every color, we scan all previous colors.

That gives:

Problem With Naive DP

The expensive step is:

min(dp[i - 1][c] for c != j)

For each color j, we repeatedly search the previous row.

But most of the time we only need:

1. The smallest value from the previous row.
2. The second smallest value.

Key Insight

Suppose the previous row is:

[7, 2, 5, 9]

Then:

Now consider computing the next row.

If the current color is not color 1, then we can safely use the global minimum:

2

But if the current color is color 1, we cannot reuse the same color.

Then we must use the second minimum:

5

So for each color:

This removes the inner scan.

Algorithm

Maintain:

For every house:

1. Compute the new DP values.
2. For each color:
   • If the color equals min1_color, use min2.
   • Otherwise use min1.
3. Add the current painting cost.
4. While computing the row, update the new smallest and second smallest values.

Walkthrough

Use:

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

House 0

Costs:

[1, 5, 3]

Minimums:

So:

min1 = 1
min2 = 3
min1_color = 0

House 1

Color 0:

Cannot reuse color 0, so use min2.

3 + 2 = 5

Color 1:

Can use min1.

1 + 9 = 10

Color 2:

Can use min1.

1 + 4 = 5

Final row:

[5, 10, 5]

Answer:

5

Correctness

For each house i and color j, the optimal previous color must be some color different from j.

The previous row contains exactly two important values:

1. The global minimum.
2. The smallest value whose color differs from j.

If j is not the color of the global minimum, then the global minimum is the best valid previous choice.

If j equals the color of the global minimum, then the global minimum cannot be used because adjacent houses cannot share a color. In this case, the second minimum is the best valid previous choice.

Thus every transition computes exactly:

costs[i][j] + minimum_valid_previous_cost

which matches the original DP recurrence.

Since every row is computed correctly from the previous row, the final minimum value is the minimum total painting cost.

Complexity

This improves over the naive:

solution.

Implementation

class Solution:
    def minCostII(self, costs: list[list[int]]) -> int:
        if not costs:
            return 0

        k = len(costs[0])

        dp = [0] * k

        for row in costs:
            new_dp = [0] * k

            min1 = float("inf")
            min2 = float("inf")
            min1_color = -1

            for color in range(k):
                value = dp[color]

                if value < min1:
                    min2 = min1
                    min1 = value
                    min1_color = color
                elif value < min2:
                    min2 = value

            for color in range(k):
                if color == min1_color:
                    new_dp[color] = row[color] + min2
                else:
                    new_dp[color] = row[color] + min1

            dp = new_dp

        return min(dp)

Code Explanation

We store the previous DP row in:

dp = [0] * k

For every house:

for row in costs:

we first find:

• smallest DP value
• second smallest DP value
• color index of the smallest value

if value < min1:

updates the smallest value.

elif value < min2:

updates the second smallest value.

Then compute the next row.

If the current color equals the minimum color:

if color == min1_color:

we must avoid reusing that color, so we use min2.

Otherwise we use min1.

Finally:

dp = new_dp

moves to the next house.

The answer is the minimum value in the final DP row.

Testing

def run_tests():
    s = Solution()

    assert s.minCostII([[1, 5, 3], [2, 9, 4]]) == 5
    assert s.minCostII([[1, 3]]) == 1
    assert s.minCostII([[8]]) == 8
    assert s.minCostII([
        [1, 2, 3],
        [1, 4, 6],
    ]) == 3

    assert s.minCostII([
        [7, 6, 2],
        [5, 8, 7],
        [3, 6, 1],
        [2, 4, 9],
    ]) == 14

    assert s.minCostII([
        [10, 3, 1, 8],
        [5, 7, 2, 9],
        [8, 1, 4, 3],
    ]) == 6

    print("all tests passed")

run_tests()

Test meaning: