Skip to main content

265. Paint House II

hard

Paint House with k colors instead of 3. The naive transition is O(n * k^2). Track the two smallest previous costs to drop it to O(n * k).

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

Problem

There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix costs. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on. Return the minimum cost to paint all houses. Follow up: Could you solve it in O(nk) runtime?

Constraints

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

Examples

Example 1

Input
costs = [[1,5,3],[2,9,4]]
Output
5

Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5. Alternatively, paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Example 2

Input
costs = [[1,3],[2,4]]
Output
5

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

Naive transition: dp[i][c] = costs[i][c] + min over c' != c of dp[i-1][c']. O(n * k^2).

Hint 2

Track only the two smallest values of the previous row plus their indices.

Hint 3

If the previous-row min was at color m1, then for c != m1 use min1; for c == m1 use min2. O(n * k).

Solution approach

Reveal approach

Track only the two smallest values from the previous row instead of the full vector. After processing row i-1 keep min1 = smallest cost, min1_idx = its color index, and min2 = second-smallest. For row i and color c: if c != min1_idx then dp[i][c] = costs[i][c] + min1, else dp[i][c] = costs[i][c] + min2. After computing the full row i, scan it once to update min1, min1_idx, and min2 for use by row i+1. Final answer is min1 after the last row. O(n * k) time, O(k) per-row scratch (or O(1) with double buffering).

Complexity

Time
O(n * k)
Space
O(k)

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 →