Skip to main content

256 - Paint House

Difficulty: Medium | Pattern: Dynamic Programming | Company tags: Facebook, Amazon, Bloomberg

Problem Statement​

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

  • costs[i][0] is the cost of painting house i red.
  • costs[i][1] is the cost of painting house i blue.
  • costs[i][2] is the cost of painting house i green.

No two adjacent houses can have the same color. Return the minimum cost to paint all houses.

Example:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 blue (2), house 1 green (5), house 2 blue (3). Total = 10.

Algorithm Flow​

Solution: DP — O(n), O(1)​

Key insight: For each house, the min cost for each color = cost[i][color] + min of the other two colors from the previous house.

def minCost(costs: list[list[int]]) -> int:
    prev_r, prev_b, prev_g = costs[0]
    
    for i in range(1, len(costs)):
        r = costs[i][0] + min(prev_b, prev_g)
        b = costs[i][1] + min(prev_r, prev_g)
        g = costs[i][2] + min(prev_r, prev_b)
        prev_r, prev_b, prev_g = r, b, g
    
    return min(prev_r, prev_b, prev_g)

Dry Run​

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

houseprev_rprev_bprev_g
017217
1r=16+min(2,17)=18, b=16+min(17,17)=33, g=5+min(17,2)=7
→18337
2r=14+min(33,7)=21, b=3+min(18,7)=10, g=19+min(18,33)=37
→211037

Result: min(21, 10, 37) = 10 ✓

Edge Cases​

  • Single house → min(costs[0])
  • All same cost → any valid sequence (no adjacency violation)

Extension: Paint House II (LC 265)​

With k colors: track the two smallest costs from previous row (O(nk) or O(n) with two-min tracking).

Complexity​

  • Time: O(n)
  • Space: O(1)

Key Terms​

TermDefinition
DP stateThe three running minimum costs (prev_r, prev_b, prev_g) representing the cheapest way to paint all houses up to i-1 ending in each color.
State transitionThe recurrence cost[i][color] + min(other two prev colors), enforcing the no-adjacent-same-color constraint.
Space-optimized DPCollapsing an O(n x 3) DP table into O(1) rolling variables since each row only depends on the previous row.
Adjacency constraintThe rule that no two consecutive houses share a color, which shapes the transition to exclude the same-color previous cost.
Rolling variablesReusing a fixed set of variables across iterations instead of an array, since only the last state is ever needed.

FAQ​

  1. Can this be solved without extra space? Yes — the space-optimized version already uses O(1) extra space via three rolling variables instead of an n x 3 table.
  2. What if the input is empty? If costs is empty (n = 0), the answer is 0 since there are no houses to paint; this edge case should be checked before indexing costs[0].
  3. How would this change if there were k colors instead of 3? Track the smallest and second-smallest cost from the previous row (with which color achieved the smallest), so each house computes its costs in O(k) instead of O(k^2) — this is exactly Paint House II (LC 265).
  4. What's the follow-up interviewers usually ask? How to generalize to k colors while keeping the update per house O(k) rather than O(k^2), and how to reconstruct the actual color assignment, not just the minimum cost.
  5. Why does the recurrence only need the previous house's costs? Because the adjacency constraint is local (only consecutive houses can't match), the optimal substructure only depends on one prior state, enabling the O(1) space rolling-variable trick.

Quick Revision​

  • Classic DP with the constraint: no two adjacent houses may share a color.
  • State: minimum cost to paint houses 0..i such that house i ends in a given color.
  • Transition: cost[i][color] + min(prev costs of the other two colors).
  • Base case: prev_r, prev_b, prev_g = costs[0] (cost of painting house 0 each color).
  • Final answer: min(prev_r, prev_b, prev_g) after processing all houses.
  • Space-optimized to O(1) since only the previous house's three costs are needed at any time.
  • Time complexity: O(n) — one constant-time update per house.
  • Generalizes to k colors (Paint House II) using top-two-minimum tracking for O(nk) time.
  • Edge case: single house just needs min(costs[0]).
  • Paint House II (LC 265) — generalizes to k colors, requiring smallest/second-smallest cost tracking.
  • House Robber (LC 198) — same "adjacent choices constrain the DP transition" pattern with rolling variables.
  • Decode Ways — another linear DP problem where each state depends only on the prior one or two states.