Paint House Problem: Minimum Cost Coloring

Key Insights

The Paint House problem demonstrates how tracking just two minimum values can reduce time complexity from O(N×K²) to O(N×K), a pattern applicable to many DP problems
Optimal substructure makes this problem tractable: the minimum cost to paint house i depends only on the minimum cost at house i-1, not the entire history
The circular variant (where first and last houses are adjacent) requires running the algorithm twice with different constraints, not a fundamentally different approach

Problem Introduction

The Paint House problem is a classic dynamic programming challenge that appears frequently in technical interviews and competitive programming. Here’s the setup: you have N houses arranged in a row, K available paint colors, and a cost matrix where costs[i][j] represents the expense of painting house i with color j. The constraint? No two adjacent houses can share the same color. Your goal is to minimize the total painting cost.

This problem models real scheduling and resource allocation scenarios—assigning tasks to workers where consecutive tasks can’t go to the same person, or allocating frequencies to cell towers where adjacent towers need different frequencies.

# Problem setup
# costs[i][j] = cost to paint house i with color j
costs = [
    [17, 2, 17],   # House 0: red=17, blue=2, green=17
    [16, 16, 5],   # House 1: red=16, blue=16, green=5
    [14, 3, 19]    # House 2: red=14, blue=3, green=19
]

# Expected output: 10
# Optimal: House 0 blue (2) + House 1 green (5) + House 2 blue (3) = 10

The input is always an N×K matrix. The output is a single integer representing the minimum total cost. Some variants ask you to return the actual color assignments, but the core algorithm remains the same.

Brute Force Approach

The naive approach explores every valid color combination. For each house, try each color that differs from the previous house’s color, recursively solve for the remaining houses, and track the minimum.

def min_cost_brute_force(costs: list[list[int]]) -> int:
    if not costs:
        return 0
    
    n, k = len(costs), len(costs[0])
    
    def solve(house: int, prev_color: int) -> int:
        if house == n:
            return 0
        
        min_cost = float('inf')
        for color in range(k):
            if color != prev_color:
                cost = costs[house][color] + solve(house + 1, color)
                min_cost = min(min_cost, cost)
        
        return min_cost
    
    # Start with prev_color=-1 (no previous constraint)
    return solve(0, -1)

This works but scales terribly. For the first house, you have K choices. For each subsequent house, you have K-1 valid choices (any color except the previous). The total combinations grow as K × (K-1)^(N-1), which is O(K^N). With 20 houses and 5 colors, you’re looking at over 1.9 trillion combinations. Unacceptable.

Identifying Overlapping Subproblems

The brute force approach recalculates the same subproblems repeatedly. Consider this call tree for 4 houses and 3 colors:

solve(0, -1)
├── solve(1, 0)  # House 0 painted red
│   ├── solve(2, 1)  # House 1 painted blue
│   │   ├── solve(3, 0)  ← Subproblem A
│   │   └── solve(3, 2)
│   └── solve(2, 2)  # House 1 painted green
│       ├── solve(3, 0)  ← Subproblem A (duplicate!)
│       └── solve(3, 1)
├── solve(1, 1)  # House 0 painted blue
│   ├── solve(2, 0)
│   │   ├── solve(3, 1)
│   │   └── solve(3, 2)
│   └── solve(2, 2)
│       ├── solve(3, 0)  ← Subproblem A (duplicate!)
│       └── solve(3, 1)
...

The subproblem solve(3, 0) (minimum cost to paint houses 3 onwards, given house 2 is red) appears multiple times. This redundancy compounds exponentially.

The key insight: the minimum cost to paint houses from index i to n-1 depends only on which color house i-1 was painted—not on the colors of houses 0 through i-2. This is optimal substructure. We can cache results based on just two parameters: the current house index and the previous color.

Dynamic Programming Solution (O(N×K²))

We’ll build a bottom-up solution using a 2D table. Define dp[i][j] as the minimum cost to paint houses 0 through i, with house i painted color j.

def min_cost_dp(costs: list[list[int]]) -> int:
    if not costs:
        return 0
    
    n, k = len(costs), len(costs[0])
    
    # dp[i][j] = min cost to paint houses 0..i with house i as color j
    dp = [[0] * k for _ in range(n)]
    
    # Base case: first house has no constraints
    for j in range(k):
        dp[0][j] = costs[0][j]
    
    # Fill the table
    for i in range(1, n):
        for j in range(k):
            # Find minimum cost from previous house with different color
            min_prev = float('inf')
            for prev_j in range(k):
                if prev_j != j:
                    min_prev = min(min_prev, dp[i-1][prev_j])
            
            dp[i][j] = costs[i][j] + min_prev
    
    # Answer is minimum cost at the last house
    return min(dp[n-1])

The recurrence relation is:

dp[0][j] = costs[0][j] (base case)
dp[i][j] = costs[i][j] + min(dp[i-1][prev_j]) for all prev_j ≠ j

Time complexity: O(N×K²). For each of the N×K cells, we scan K-1 previous values. Space complexity: O(N×K) for the DP table, reducible to O(K) since we only need the previous row.

def min_cost_dp_space_optimized(costs: list[list[int]]) -> int:
    if not costs:
        return 0
    
    n, k = len(costs), len(costs[0])
    prev = costs[0][:]  # Previous row
    
    for i in range(1, n):
        curr = [0] * k
        for j in range(k):
            min_prev = min(prev[pj] for pj in range(k) if pj != j)
            curr[j] = costs[i][j] + min_prev
        prev = curr
    
    return min(prev)

Optimized O(N×K) Solution

Here’s where it gets interesting. For each house, we’re finding the minimum of the previous row excluding one element. Instead of scanning all K elements each time, we can precompute the two smallest values from the previous row.

Why two? If the current color matches the index of the minimum, we use the second minimum. Otherwise, we use the minimum. Two values cover all cases.

def min_cost_optimized(costs: list[list[int]]) -> int:
    if not costs:
        return 0
    
    n, k = len(costs), len(costs[0])
    
    # Track: minimum value, its index, and second minimum value
    min1, min1_idx, min2 = 0, -1, 0
    
    for i in range(n):
        new_min1, new_min1_idx, new_min2 = float('inf'), -1, float('inf')
        
        for j in range(k):
            # Use min1 unless current color matches min1's index
            prev_min = min1 if j != min1_idx else min2
            cost = costs[i][j] + prev_min
            
            # Update the two minimums for next iteration
            if cost < new_min1:
                new_min2 = new_min1
                new_min1, new_min1_idx = cost, j
            elif cost < new_min2:
                new_min2 = cost
        
        min1, min1_idx, min2 = new_min1, new_min1_idx, new_min2
    
    return min1

Time complexity drops to O(N×K). Space complexity is O(1)—we’re only storing three values regardless of input size. This optimization is significant when K is large.

Variations and Extensions

Circular Houses (First and Last Adjacent)

When houses form a circle, the first and last houses can’t share colors. The trick: run the algorithm twice. Once forcing house 0 to use colors 0 to K-2 (excluding the last color), and once forcing it to use only the last color. Take the minimum.

A cleaner approach: run the algorithm twice, once excluding the first house and once excluding the last house.

def min_cost_circular(costs: list[list[int]]) -> int:
    if len(costs) == 1:
        return min(costs[0])
    
    def solve(costs_subset: list[list[int]], first_color: int) -> int:
        """Solve with first house fixed to first_color."""
        n, k = len(costs_subset), len(costs_subset[0])
        
        # Initialize: first house must be first_color
        min1 = costs_subset[0][first_color]
        min1_idx = first_color
        min2 = float('inf')
        
        for i in range(1, n):
            new_min1, new_min1_idx, new_min2 = float('inf'), -1, float('inf')
            
            for j in range(k):
                prev_min = min1 if j != min1_idx else min2
                cost = costs_subset[i][j] + prev_min
                
                if cost < new_min1:
                    new_min2 = new_min1
                    new_min1, new_min1_idx = cost, j
                elif cost < new_min2:
                    new_min2 = cost
            
            min1, min1_idx, min2 = new_min1, new_min1_idx, new_min2
        
        # Last house can't match first_color
        return min2 if min1_idx == first_color else min1
    
    # Try each color for the first house
    return min(solve(costs, c) for c in range(len(costs[0])))

Three Colors Special Case (LeetCode 256)

When K=3, the solution simplifies since there are only two valid previous colors for each current color:

def min_cost_three_colors(costs: list[list[int]]) -> int:
    r, g, b = 0, 0, 0
    
    for cr, cg, cb in costs:
        r, g, b = cr + min(g, b), cg + min(r, b), cb + min(r, g)
    
    return min(r, g, b)

Complexity Analysis & Key Takeaways

Approach	Time	Space
Brute Force	O(K^N)	O(N) recursion stack
Memoized Recursion	O(N×K²)	O(N×K)
Bottom-up DP	O(N×K²)	O(N×K) or O(K)
Optimized DP	O(N×K)	O(1)

The jump from O(N×K²) to O(N×K) comes from recognizing that we don’t need all K previous values—just the two smallest. This pattern appears in many DP problems where you’re taking minimums or maximums while excluding specific indices.

Key patterns to recognize:

State compression: When only the previous row matters, reduce from 2D to 1D storage
Tracking extremes: When you need min/max excluding one element, track the top two values
Circular constraints: Often solvable by running linear algorithms multiple times with different boundary conditions

The Paint House problem is a gateway to understanding these optimization techniques. Master it, and you’ll recognize the same patterns in problems involving task scheduling, resource allocation, and sequence optimization.