Example 1
ready- Input
costs = [ [ 17, 2, 17 ], [ 16, 16, 5 ], [ 14, 3, 19 ] ]- Expected
10- Why
- blue, green, blue costs 2 + 5 + 3 = 10
Paint House
35 min · minCost()mediumOpen in LeetCode #256 ↗
Painting one house cheaply is easy. Painting an entire street cheaply gets interesting when every choice changes what you're allowed to do next door.
You're given a matrix, a grid of rows and columns, named costs. Row i holds the
price of painting house i red, blue, or green, in that order:
costs[i] = [red, blue, green].
Choose one color for every house and return the smallest possible total cost.
A few ground rules:
- Adjacent houses are neighbors whose indices differ by one. They must receive different colors.
- Every house must be painted exactly once.
- A paint cost may be zero.
Constraints
1 <= costs.length <= 100- Every row in
costscontains exactly3integers. 0 <= costs[i][color] <= 1_000
Hints
Your last choice is enough
When you reach a house, does the full painting history matter? Only the previous house's color can block your next move.
Write three running answers
Track the cheapest total ending in red, blue, and green. A new red total may extend only the previous blue or green total.
Roll the row forward
Compute all three new totals from the old three before replacing them. After the last house, the answer is the smallest of the three totals.
Follow-up
What changes when the paint shop offers k colors? Can you avoid checking all other
k - 1 colors every time you update one color?
Visible cases
Examples
Example 2
ready- Input
costs = [ [ 5, 8, 6 ] ]- Expected
5- Why
- one house has no neighbor to conflict with
Example 3
ready- Input
costs = [ [ 3, 1, 4 ], [ 2, 8, 5 ] ]- Expected
3- Why
- blue then red costs 1 + 2 = 3
Interview signal
Asked at
AmazonGoogle
Memoized recursion
At house i, the only past detail that affects your choices is the color used at
house i - 1.
Dynamic programming (DP) stores answers to repeated subproblems so you compute each
state once. A DP state is the small set of facts that identifies one subproblem;
here, that state is (house, last_color). Memoization means caching each solved
state. Try every color except last_color, pay its cost, and ask the same question for
the next house, then memoize the cheapest result.
def min_cost(costs: list[list[int]]) -> int:
memo: dict[tuple[int, int], int] = {}
def solve(house: int, last_color: int) -> int:
if house == len(costs):
return 0
state = (house, last_color)
if state in memo:
return memo[state]
best = float("inf")
for color in range(3):
if color != last_color:
total = costs[house][color] + solve(house + 1, color)
best = min(best, total)
memo[state] = int(best)
return memo[state]
return solve(0, -1)There are only n × 4 reachable states: three previous colors plus the initial
-1 state. Each state considers three colors.
Time O(n). Space O(n) for the memo and recursion stack.
Rolling three-color DP
The recursive state points only one house backward, so you don't need to retain the whole memo. Keep three totals instead:
redis the cheapest valid cost so far when the latest house is red.blueandgreenmean the same for their colors.
To paint the next house red, extend the cheaper of the previous blue and green totals. The other two updates follow the same rule.
def min_cost(costs: list[list[int]]) -> int:
red, blue, green = costs[0]
for red_cost, blue_cost, green_cost in costs[1:]:
next_red = red_cost + min(blue, green)
next_blue = blue_cost + min(red, green)
next_green = green_cost + min(red, blue)
red, blue, green = next_red, next_blue, next_green
return min(red, blue, green)All three next totals must come from the old row. Assigning them together prevents a freshly updated value from leaking into another color's calculation.
Time O(n). Space O(1) — three running totals replace the full table.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
10
Run: visible + custom · Submit: full suite