LeetCode 256: Paint House

Problem Restatement

We are given n houses in a row.

Each house can be painted one of three colors:

The painting cost is given by an n x 3 matrix called costs.

For example:

costs[i][0]

is the cost to paint house i red.

We need to paint every house such that no two adjacent houses have the same color.

Return the minimum total cost.

The constraints are costs.length == n, costs[i].length == 3, 1 <= n <= 100, and 1 <= costs[i][j] <= 20. The standard examples include [[17,2,17],[16,16,5],[14,3,19]] -> 10 and [[7,6,2]] -> 2.

Input and Output

Example function shape:

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

Examples

Example 1:

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

One optimal painting is:

Total cost:

2 + 5 + 3 = 10

Answer:

10

Example 2:

costs = [[7, 6, 2]]

There is only one house.

Choose the cheapest color.

Answer:

2

First Thought: Try Every Coloring

A direct solution is to try every possible color for every house.

For each house, there are three choices.

So for n houses, the number of possible colorings is:

3 ** n

Then we keep only the colorings where adjacent houses use different colors and take the cheapest one.

This gives the right answer, but it is far too slow.

Problem With Brute Force

The brute force search repeats the same decisions many times.

For example, after painting the first few houses, the only information that matters for the next house is:

1. The previous house’s color.
2. The minimum cost so far.

We do not need to remember the full color sequence.

That is the dynamic programming structure.

Key Insight

For each house, track three values:

When painting the current house red, the previous house cannot be red.

So the best cost ending in red is:

min(previous_blue, previous_green) + current_red_cost

Similarly:

new_blue = min(previous_red, previous_green) + current_blue_cost
new_green = min(previous_red, previous_blue) + current_green_cost

This is enough because future houses only care about the color of the immediately previous house.

Algorithm

Start with:

red = blue = green = 0

These variables represent the minimum cost before painting any house.

For each row:

cost_red, cost_blue, cost_green

compute the new totals:

new_red = min(blue, green) + cost_red
new_blue = min(red, green) + cost_blue
new_green = min(red, blue) + cost_green

Then update:

red = new_red
blue = new_blue
green = new_green

After all houses are processed, return:

min(red, blue, green)

Walkthrough

Use:

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

Before any house:

red = 0
blue = 0
green = 0

After house 0:

red = 17
blue = 2
green = 17

After house 1:

red = min(2, 17) + 16 = 18
blue = min(17, 17) + 16 = 33
green = min(17, 2) + 5 = 7

So:

red = 18
blue = 33
green = 7

After house 2:

red = min(33, 7) + 14 = 21
blue = min(18, 7) + 3 = 10
green = min(18, 33) + 19 = 37

Final answer:

min(21, 10, 37) = 10

Correctness

For each house i, maintain this invariant:

red, blue, and green store the minimum cost to paint houses 0 through i when house i is painted red, blue, or green respectively.

The invariant is true after the first house because the cost is simply the cost of painting that house with each color.

Assume it is true for the previous house.

For the current house, if we paint it red, the previous house must be blue or green. The cheapest valid previous total is therefore:

min(previous_blue, previous_green)

Adding the current red cost gives the cheapest valid total ending in red.

The same reasoning applies to blue and green.

Thus the invariant remains true after every house.

At the end, the last house may have any color, so the minimum valid total is:

min(red, blue, green)

Therefore the algorithm returns the minimum total painting cost.

Complexity

Implementation

class Solution:
    def minCost(self, costs: list[list[int]]) -> int:
        red = blue = green = 0

        for cost_red, cost_blue, cost_green in costs:
            red, blue, green = (
                min(blue, green) + cost_red,
                min(red, green) + cost_blue,
                min(red, blue) + cost_green,
            )

        return min(red, blue, green)

Code Explanation

We initialize all three states to zero:

red = blue = green = 0

This means no cost has been paid before painting the first house.

For each house:

for cost_red, cost_blue, cost_green in costs:

we compute the minimum cost ending with each color.

The assignment:

red, blue, green = (
    min(blue, green) + cost_red,
    min(red, green) + cost_blue,
    min(red, blue) + cost_green,
)

uses the old values of red, blue, and green on the right side before updating them.

This is important. It prevents the new red value from accidentally affecting the computation of blue or green.

Finally:

return min(red, blue, green)

returns the cheapest valid total after painting all houses.

Testing

def run_tests():
    s = Solution()

    assert s.minCost([[17, 2, 17], [16, 16, 5], [14, 3, 19]]) == 10
    assert s.minCost([[7, 6, 2]]) == 2
    assert s.minCost([[1, 5, 3], [2, 9, 4]]) == 5
    assert s.minCost([[5, 8, 6], [19, 14, 13], [7, 5, 12]]) == 24
    assert s.minCost([[20, 18, 4], [9, 9, 10], [6, 2, 8], [6, 2, 19]]) == 22

    print("all tests passed")

run_tests()

Test meaning: