Paint House II
MediumTrack the best two previous colours
Problem
Paint houses with k colors so no two adjacent match, minimizing cost (in O(n*k)).
For each house pick the cheapest colour different from the previous house's chosen colour.
The idea
With k colours, scanning all of them for each colour costs O(n·k²). Keeping the smallest and second-smallest previous totals is enough: use the smallest unless it is the same colour, in which case use the second — giving O(n·k).
The trick
- The second-smallest exists precisely to handle the same-colour clash.
- O(n·k) instead of O(n·k²).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — k colors Values: 0.
1keep min1,min2 of previous row2dp[i][c]=cost[i][c]+(min1 if c!=argmin else min2)Input
- array
- [0]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- costs = [[1,5,3],[2,9,4]]
- Output:
- 5
- Explanation:
- Best two-house colouring costs 5.
Example 2
- Input:
- costs = [[1,3],[2,4]]
- Output:
- 5
- Explanation:
- Alternate colours → 1+4 or 3+2 = 5.
Example 3
- Input:
- costs = [[5]]
- Output:
- 5
- Explanation:
- One house, one colour → 5.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.