Skip to main content

256. Paint House

medium

Paint n houses red, blue, or green so that no two neighbors share a color, minimizing cost. Three rolling DP scalars — one per color.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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 different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs. For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on. Return the minimum cost to paint all houses.

Constraints

  • costs.length == n
  • costs[i].length == 3
  • 1 <= n <= 100
  • 1 <= costs[i][j] <= 20

Examples

Example 1

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

Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.

Example 2

Input
costs = [[7,6,2]]
Output
2

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Track three rolling values: min cost so far if last house was painted red, blue, or green.

Hint 2

Transition for house i: red = costs[i][0] + min(prev_blue, prev_green). Symmetric for blue and green.

Hint 3

Return min(final three).

Solution approach

Reveal approach

Three rolling values r, b, g representing the minimum cost to paint houses 0..i so that house i is red, blue, or green respectively. Initialize from costs[0]. For each subsequent house i compute new values using only the previous: new_r = costs[i][0] + min(prev_b, prev_g); new_b = costs[i][1] + min(prev_r, prev_g); new_g = costs[i][2] + min(prev_r, prev_b). After processing every house, return min(r, b, g). O(n) time, O(1) space. The adjacency constraint is naturally encoded by excluding the current color from the previous state's min.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Facebook
  • LinkedIn

More DP 1D practice problems

See all DP 1D problems →