This practice workspace is built for desktop. Open it on a larger screen to start solving.

Paint House II

Dynamic Programming·Hard

There are n houses in a row. Each house can be painted one of k colors. The cost of painting house i with color j is costs[i][j]. Adjacent houses cannot have the same color.

Return the minimum total painting cost.

Optimize to O(n·k): at each row, track the two smallest accumulated costs so that updating any color only needs O(1) lookup — you use the overall minimum when the previous color differs, or the second minimum when it matches.

Examples

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

Output: 5

Paint house 0 red (1), house 1 green (4). Total = 5.

Input: costs = [[1,3],[3,1]]

Output: 2

Paint house 0 color 0 (1) and house 1 color 1 (1). Total = 2.

Constraints

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

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Dynamic Programming
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.