DP — Paint House II
↗ LeetCode: Paint House II · Hard · pattern chapter →
Asked atLinkedInFacebookMetaGoogle
n houses, k colors. cost to paint. No two adjacent same color. Min total.
Constraints — 1 ≤ n·k ≤ 5000. Brute recursion tries k colors at each of n houses — O(k^n) = k¹⁰⁰⁰⁰ at max, ~10⁹⁰⁰⁰ ops (dies before 10⁵⁰⁰⁰ year). DP with "best + second-best previous color" trick is O(n·k) ≤ 5·10³ ops, scales to ~10⁶ ops/sec queries. Example 1 — costs=[[1,5,3],[2,9,4]] → 5Example 2 — costs=[[1,3],[2,4]] → 5
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — O(n · k²) DP
dp[i][j] = cost[i][j] + min(dp[i-1][j']) over j' ≠ j.
Approach 2 — Track min & second-min per row → O(n · k) (canonical)
Insight. Only need two smallest values from previous row + which index was min.
java
int minCostII(int[][] costs) {
int n = costs.length, k = costs[0].length;
int min1 = 0, min2 = 0, idx1 = -1;
for (int i = 0; i < n; i++) {
int nMin1 = Integer.MAX_VALUE, nMin2 = Integer.MAX_VALUE, nIdx1 = -1;
for (int j = 0; j < k; j++) {
int c = costs[i][j] + (j == idx1 ? min2 : min1);
if (c < nMin1) { nMin2 = nMin1; nMin1 = c; nIdx1 = j; }
else if (c < nMin2) nMin2 = c;
}
min1 = nMin1; min2 = nMin2; idx1 = nIdx1;
}
return min1;
}Execution Trace
Step 1 / 3Initialize scan.
Complexity — Time O(n · k); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| O(n·k²) DP | O(n·k²) | O(k) | baseline |
| Min+second min | O(n·k) | O(1) | canonical |
When to use which
- Standard → min + second-min trick.
- Only 3 colors → O(n) with 3-way check.
- Return coloring → track color chosen.
AI Study CompanionBeta
Related problems
Was this page helpful?