LeetCode 256 - Paint House

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us a row of houses, where each house must be painted using exactly one of three colors: red, blue, or green. The input is provided as a two-dimensional array named costs, where costs[i][j] represents the cost of painting the i-th house with the j-th color.

The goal is to paint every house while satisfying one important constraint: no two adjacent houses may share the same color. Among all valid painting combinations, we must return the minimum possible total cost.

For example, if house 0 is painted blue, then house 1 cannot also be painted blue. This restriction applies only to neighboring houses, not to houses farther apart.

The constraints are relatively small:

There are at most 100 houses.
Each painting cost is between 1 and 20.
Every house always has exactly three color choices.

Even though the constraints are not extremely large, a naive brute-force approach would still become inefficient because each house introduces three branching choices. This naturally suggests a dynamic programming solution, because the optimal decision for one house depends only on the previous house.

Several important edge cases should be considered:

A single house, where the answer is simply the minimum among the three painting costs.
Multiple houses where one color repeatedly appears cheapest, but cannot always be chosen due to adjacency restrictions.
Inputs where costs are equal across colors, requiring the algorithm to correctly handle ties.
Very small arrays, which can expose indexing mistakes or incorrect initialization.

The problem guarantees that the input matrix is valid and always contains exactly three columns, so we do not need to handle malformed input.

Approaches

Brute-Force Approach

A straightforward solution is to try every possible valid coloring combination.

For each house, we choose one of the three colors while ensuring it differs from the previous house's color. We recursively explore every valid possibility and compute the total cost for each complete painting arrangement. The minimum among all valid arrangements is the answer.

This approach is correct because it exhaustively checks every valid coloring configuration. However, it is inefficient because each house introduces multiple branching choices. In the worst case, the total number of combinations grows exponentially.

More specifically, the first house has 3 choices, and each subsequent house has roughly 2 valid choices because it cannot match the previous color. This produces approximately 3 × 2^(n-1) combinations.

Although n <= 100 is not enormous, exponential growth quickly becomes impractical.

Dynamic Programming Insight

The key observation is that when deciding how to paint the current house, we only care about the minimum cost of painting the previous house with a different color.

Suppose we want to paint house i red. Then the previous house must have been painted either blue or green. Therefore:

Cost to paint current house red =

current red cost +

minimum(previous blue total, previous green total)

The same logic applies for blue and green.

This structure reveals overlapping subproblems:

The minimum cost up to house i depends only on the minimum costs up to house i-1.

Instead of recomputing these values repeatedly, we store them and build the answer incrementally.

This transforms the solution from exponential time into linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores all valid color assignments
Optimal Dynamic Programming	O(n)	O(1)	Tracks minimum cumulative costs for each color

Algorithm Walkthrough

Initialize three variables representing the minimum cumulative cost of painting the previous house red, blue, and green.

For the first house, these values are simply the painting costs from costs[0]. 2. Iterate through the remaining houses one by one.

For each house, calculate three new values:

The minimum total cost if the current house is painted red.
The minimum total cost if the current house is painted blue.
The minimum total cost if the current house is painted green.

When computing the cost for one color, add the current painting cost to the minimum of the other two previous colors.

For example:

Current red cost =

current red painting cost +

minimum(previous blue total, previous green total)

This enforces the rule that adjacent houses cannot share the same color. 4. After computing the new totals, replace the previous values with the newly computed values.

At this point, the variables represent the optimal cumulative costs up to the current house. 5. Continue this process until all houses have been processed. 6. After the final house, return the minimum among the three cumulative color totals.

This represents the cheapest valid way to paint all houses.

Why it works

The algorithm maintains the invariant that after processing house i, each stored value represents the minimum possible total cost for painting houses 0 through i, with house i painted a specific color.

Because every transition only allows different adjacent colors, all generated states remain valid. Since each state always chooses the minimum valid previous configuration, the final answer is globally optimal.

Python Solution

from typing import List

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

        red, blue, green = costs[0]

        for i in range(1, len(costs)):
            current_red = costs[i][0] + min(blue, green)
            current_blue = costs[i][1] + min(red, green)
            current_green = costs[i][2] + min(red, blue)

            red = current_red
            blue = current_blue
            green = current_green

        return min(red, blue, green)

The implementation begins by handling the edge case where the input is empty. Although the constraints guarantee at least one house, defensive handling makes the function more robust.

The variables red, blue, and green store the minimum cumulative costs for the previous house.

For every subsequent house, the algorithm computes three new totals:

If the current house is painted red, the previous house must have been blue or green.
If the current house is painted blue, the previous house must have been red or green.
If the current house is painted green, the previous house must have been red or blue.

The variables are then updated in place, which allows the algorithm to use constant extra space.

Finally, the smallest among the three totals is returned because the last house may end with any valid color.

Go Solution

func minCost(costs [][]int) int {
    if len(costs) == 0 {
        return 0
    }

    red := costs[0][0]
    blue := costs[0][1]
    green := costs[0][2]

    for i := 1; i < len(costs); i++ {
        currentRed := costs[i][0] + min(blue, green)
        currentBlue := costs[i][1] + min(red, green)
        currentGreen := costs[i][2] + min(red, blue)

        red = currentRed
        blue = currentBlue
        green = currentGreen
    }

    return min(red, min(blue, green))
}

func min(a int, b int) int {
    if a < b {
        return a
    }

    return b
}

The Go implementation follows the same dynamic programming logic as the Python version. Since Go does not provide a built-in min function for integers, a helper function is defined.

Go slices are used naturally for the two-dimensional input array. Integer overflow is not a concern because the maximum possible cost is very small:

Maximum cost per house = 20
Maximum houses = 100
Maximum total = 2000

This comfortably fits within Go's integer range.

Worked Examples

Example 1

Input:

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

Initial state from house 0:

House	Red	Blue	Green
0	17	2	17

Now process house 1.

Paint house 1 red

16 + min(2, 17) = 18

Paint house 1 blue

16 + min(17, 17) = 33

Paint house 1 green

5 + min(17, 2) = 7

Updated state:

House	Red	Blue	Green
1	18	33	7

Now process house 2.

Paint house 2 red

14 + min(33, 7) = 21

Paint house 2 blue

3 + min(18, 7) = 10

Paint house 2 green

19 + min(18, 33) = 37

Final state:

House	Red	Blue	Green
2	21	10	37

Final answer:

min(21, 10, 37) = 10

Example 2

Input:

costs = [[7,6,2]]

Initial state:

House	Red	Blue	Green
0	7	6	2

There are no additional houses to process.

Final answer:

min(7, 6, 2) = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each house is processed exactly once
Space	O(1)	Only three running totals are stored

The algorithm performs a constant amount of work for every house. Since there are n houses, the total running time grows linearly.

The space usage remains constant because we only maintain three cumulative cost variables regardless of input size.

Test Cases

from typing import List

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

        red, blue, green = costs[0]

        for i in range(1, len(costs)):
            current_red = costs[i][0] + min(blue, green)
            current_blue = costs[i][1] + min(red, green)
            current_green = costs[i][2] + min(red, blue)

            red = current_red
            blue = current_blue
            green = current_green

        return min(red, blue, green)

solution = Solution()

assert solution.minCost([[17,2,17],[16,16,5],[14,3,19]]) == 10
# Provided example with multiple houses

assert solution.minCost([[7,6,2]]) == 2
# Single house case

assert solution.minCost([[1,1,1],[1,1,1]]) == 2
# Equal costs across all colors

assert solution.minCost([[1,100,100],[100,1,100],[100,100,1]]) == 3
# Optimal path alternates colors perfectly

assert solution.minCost([[5,8,6],[19,14,13],[7,5,12],[14,15,17],[3,20,10]]) == 43
# Larger mixed-cost example

assert solution.minCost([[1,2,3],[1,2,3],[3,3,1]]) == 4
# Requires avoiding locally cheapest repeated color

assert solution.minCost([[20,18,4],[9,9,10]]) == 13
# Small two-house case

assert solution.minCost([]) == 0
# Defensive empty input handling

Test	Why
`[[17,2,17],[16,16,5],[14,3,19]]`	Validates the primary example
`[[7,6,2]]`	Tests single-house behavior
`[[1,1,1],[1,1,1]]`	Confirms correct handling of equal costs
`[[1,100,100],[100,1,100],[100,100,1]]`	Tests ideal alternating path
Larger mixed-cost example	Verifies correctness across many transitions
`[[1,2,3],[1,2,3],[3,3,1]]`	Ensures adjacency restriction is enforced
`[[20,18,4],[9,9,10]]`	Tests minimal two-row transitions
`[]`	Verifies defensive handling of empty input

Edge Cases

Single House

When there is only one house, there are no adjacency constraints because there are no neighboring houses. The correct answer is simply the minimum among the three painting costs.

This case can expose incorrect loop initialization or off-by-one errors. The implementation handles it naturally because the loop begins at index 1, so no iterations occur.

Repeated Cheapest Color

A common mistake is greedily choosing the cheapest color for each house independently. This fails when adjacent houses would end up sharing the same color.

For example:

[[1,100,100],
 [1,100,100]]

A greedy approach might incorrectly choose red twice. The dynamic programming solution avoids this because each state transition explicitly excludes the same previous color.

Equal Costs Across Colors

When all painting costs are equal, multiple optimal solutions exist.

For example:

[[1,1,1],
 [1,1,1]]

The algorithm must still correctly enforce adjacency constraints while computing the minimum total cost.

Because the solution always computes transitions using valid previous colors only, ties are handled naturally and correctly.

Empty Input

Although the official constraints guarantee at least one house, robust implementations often defensively handle empty input.

Returning 0 for an empty array prevents runtime errors and makes the function safer in non-LeetCode environments.