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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Paint House II and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →