LeetCode 265 - Paint House II
The problem gives us a matrix called costs, where costs[i][j] represents the cost of painting house i with color j. We must paint every house such that no two adjacent houses use the same color, and we want the minimum total painting cost.
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming
Solution
Problem Understanding
The problem gives us a matrix called costs, where costs[i][j] represents the cost of painting house i with color j. We must paint every house such that no two adjacent houses use the same color, and we want the minimum total painting cost.
If there are n houses and k colors, then the matrix has dimensions n x k. Every row corresponds to a house, and every column corresponds to a color choice for that house.
The key restriction is that neighboring houses cannot share the same color. This means that when we choose a color for house i, we cannot reuse the color selected for house i - 1.
The output is a single integer, the minimum possible total cost while satisfying the adjacency constraint.
The constraints are important:
n <= 100k <= 20
A brute force solution that tries every possible coloring would require checking k^n combinations, which becomes infeasible very quickly. Even with only 20 colors and 100 houses, exhaustive search is impossible.
The relatively small value of k suggests that dynamic programming is appropriate, because we can efficiently track the best cost for each color choice at each house.
Several edge cases are important:
- A single house, where we simply choose the cheapest color.
- Many colors but very few houses.
- Cases where the globally cheapest color cannot be reused because adjacent houses must differ.
- Situations where multiple colors tie for minimum cost.
- Very small
k, especiallyk = 2, where alternating constraints become tight.
The problem guarantees that k >= 2, so there is always at least one valid color choice for the next house.
Approaches
Brute Force
A brute force approach would recursively try every possible color assignment for every house.
For each house, we attempt all colors except the one used by the previous house. Once we reach the final house, we compute the total cost and track the minimum across all valid combinations.
This approach is correct because it explicitly explores every valid painting arrangement. Since the optimal solution must be one of those arrangements, brute force eventually finds it.
However, the runtime is exponential. For each house we may have up to k choices, leading to roughly O(k^n) possibilities. This becomes computationally impossible for the maximum constraints.
Dynamic Programming Insight
The important observation is that the choice for the current house only depends on the previous house.
Define:
dp[i][j]= minimum cost to paint houses0...iwhere houseiuses colorj
The transition is:
dp[i][j] = costs[i][j] + min(dp[i-1][c]) for all c != j
A straightforward implementation would compute the minimum over all previous colors for every state, resulting in O(n * k^2) time.
The follow-up asks for O(nk) runtime. The optimization comes from noticing that for every row we only need:
- The smallest value from the previous row
- The second smallest value from the previous row
- The color index of the smallest value
Then:
- If current color
jis not the previous minimum color, use the previous minimum. - Otherwise, use the previous second minimum.
This avoids scanning all colors repeatedly.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(k^n) | O(n) | Tries every valid color assignment recursively |
| Optimal | O(nk) | O(1) extra space | Tracks minimum and second minimum values dynamically |
Algorithm Walkthrough
- Handle the empty input case.
If costs is empty, there are no houses to paint, so the answer is 0.
2. Initialize the first row.
For the first house, the minimum cost for each color is simply the painting cost itself because there are no previous houses. 3. Track the smallest and second smallest costs.
For each processed row, maintain:
min1, the smallest cumulative costmin2, the second smallest cumulative costmin1_color, the color index associated withmin1
These values summarize everything needed from the previous row. 4. Process each house one by one.
For every color in the current house:
- If the color is different from
min1_color, we can safely extend the globally cheapest previous configuration. - Otherwise, we must use
min2because adjacent houses cannot share the same color.
- Compute the new cumulative cost.
The transition becomes:
current_cost = costs[i][j] + best_previous
where best_previous is either min1 or min2.
6. Update the current row's minimums.
As we compute values for the current house, we continuously update:
- the new smallest cumulative cost
- the new second smallest cumulative cost
- the associated color index
- Move to the next house.
After processing all colors for the current house, the new minimum values become the previous minimum values for the next iteration. 8. Return the final minimum.
After processing all houses, min1 contains the minimum total painting cost.
Why it works
The dynamic programming invariant is:
min1 = minimum cumulative cost for all processed houses
min2 = second minimum cumulative cost
For each color, the only forbidden transition is using the same color as the previous house. Therefore:
- If the cheapest previous configuration used a different color, it is optimal to extend it.
- Otherwise, the second cheapest valid configuration must be used.
Because every state transition preserves the adjacency constraint and always chooses the optimal valid predecessor, the final result is globally optimal.
Python Solution
from typing import List
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
if not costs:
return 0
n = len(costs)
k = len(costs[0])
prev_min1 = 0
prev_min2 = 0
prev_min1_color = -1
for house in range(n):
curr_min1 = float('inf')
curr_min2 = float('inf')
curr_min1_color = -1
for color in range(k):
if color == prev_min1_color:
current_cost = costs[house][color] + prev_min2
else:
current_cost = costs[house][color] + prev_min1
if current_cost < curr_min1:
curr_min2 = curr_min1
curr_min1 = current_cost
curr_min1_color = color
elif current_cost < curr_min2:
curr_min2 = current_cost
prev_min1 = curr_min1
prev_min2 = curr_min2
prev_min1_color = curr_min1_color
return prev_min1
The implementation begins by handling the empty input case. Although the constraints guarantee at least one house, defensive programming keeps the solution robust.
The variables prev_min1, prev_min2, and prev_min1_color summarize the previous DP row. Instead of storing an entire dp matrix, we only retain the information needed for transitions.
For each house, the algorithm computes the best cumulative cost for every color. If the current color matches the previous minimum color, the algorithm uses prev_min2 to avoid violating the adjacency rule. Otherwise, it safely extends the globally cheapest configuration.
While computing the current row, the algorithm continuously updates the smallest and second smallest cumulative costs. This allows the next iteration to run in constant time per color.
At the end, prev_min1 contains the minimum achievable total cost.
Go Solution
package main
import "math"
func minCostII(costs [][]int) int {
if len(costs) == 0 {
return 0
}
n := len(costs)
k := len(costs[0])
prevMin1 := 0
prevMin2 := 0
prevMin1Color := -1
for house := 0; house < n; house++ {
currMin1 := math.MaxInt32
currMin2 := math.MaxInt32
currMin1Color := -1
for color := 0; color < k; color++ {
currentCost := 0
if color == prevMin1Color {
currentCost = costs[house][color] + prevMin2
} else {
currentCost = costs[house][color] + prevMin1
}
if currentCost < currMin1 {
currMin2 = currMin1
currMin1 = currentCost
currMin1Color = color
} else if currentCost < currMin2 {
currMin2 = currentCost
}
}
prevMin1 = currMin1
prevMin2 = currMin2
prevMin1Color = currMin1Color
}
return prevMin1
}
The Go implementation follows the same logic as the Python version. Since Go does not provide float('inf'), the solution uses math.MaxInt32 as a large sentinel value.
Slices are used naturally for the input matrix, and integer overflow is not a concern because the maximum possible total cost is small:
100 houses * max cost 20 = 2000
The implementation also handles the empty input case safely.
Worked Examples
Example 1
Input:
costs = [[1,5,3],[2,9,4]]
Initial state:
| Variable | Value |
|---|---|
| prev_min1 | 0 |
| prev_min2 | 0 |
| prev_min1_color | -1 |
Process house 0.
| Color | Cost Calculation | Result |
|---|---|---|
| 0 | 1 + 0 | 1 |
| 1 | 5 + 0 | 5 |
| 2 | 3 + 0 | 3 |
After house 0:
| Variable | Value |
|---|---|
| prev_min1 | 1 |
| prev_min2 | 3 |
| prev_min1_color | 0 |
Process house 1.
For color 0, we cannot reuse previous minimum color 0, so use prev_min2.
| Color | Cost Calculation | Result |
|---|---|---|
| 0 | 2 + 3 | 5 |
| 1 | 9 + 1 | 10 |
| 2 | 4 + 1 | 5 |
Final minimum cost:
5
Example 2
Input:
costs = [[1,3],[2,4]]
Process house 0.
| Color | Result |
|---|---|
| 0 | 1 |
| 1 | 3 |
Minimums:
| Variable | Value |
|---|---|
| prev_min1 | 1 |
| prev_min2 | 3 |
| prev_min1_color | 0 |
Process house 1.
| Color | Calculation | Result |
|---|---|---|
| 0 | 2 + 3 | 5 |
| 1 | 4 + 1 | 5 |
Answer:
5
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(nk) | Each house and color combination is processed exactly once |
| Space | O(1) extra space | Only a few tracking variables are stored |
The algorithm avoids the naive O(k) scan for every transition by maintaining the smallest and second smallest cumulative costs from the previous row. This optimization reduces the overall runtime from O(nk^2) to O(nk).
The solution uses constant extra space because it does not allocate a DP table. Only a fixed number of variables are maintained regardless of input size.
Test Cases
from typing import List
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
if not costs:
return 0
n = len(costs)
k = len(costs[0])
prev_min1 = 0
prev_min2 = 0
prev_min1_color = -1
for house in range(n):
curr_min1 = float('inf')
curr_min2 = float('inf')
curr_min1_color = -1
for color in range(k):
if color == prev_min1_color:
current_cost = costs[house][color] + prev_min2
else:
current_cost = costs[house][color] + prev_min1
if current_cost < curr_min1:
curr_min2 = curr_min1
curr_min1 = current_cost
curr_min1_color = color
elif current_cost < curr_min2:
curr_min2 = current_cost
prev_min1 = curr_min1
prev_min2 = curr_min2
prev_min1_color = curr_min1_color
return prev_min1
solution = Solution()
assert solution.minCostII([[1,5,3],[2,9,4]]) == 5 # provided example 1
assert solution.minCostII([[1,3],[2,4]]) == 5 # provided example 2
assert solution.minCostII([[7,2,9]]) == 2 # single house
assert solution.minCostII([[1,2],[2,1],[1,2]]) == 3 # alternating colors
assert solution.minCostII([[5,5,5],[5,5,5]]) == 10 # equal costs everywhere
assert solution.minCostII([[1,100,100],[100,1,100],[100,100,1]]) == 3 # diagonal minimum
assert solution.minCostII([[8,16],[19,18],[8,5],[15,9]]) == 40 # multiple transitions
assert solution.minCostII([]) == 0 # empty input defensive case
Test Summary
| Test | Why |
|---|---|
[[1,5,3],[2,9,4]] |
Validates standard multi-color scenario |
[[1,3],[2,4]] |
Tests smallest allowed number of colors |
[[7,2,9]] |
Verifies single-house handling |
[[1,2],[2,1],[1,2]] |
Ensures alternating constraints work |
[[5,5,5],[5,5,5]] |
Tests tied minimum values |
[[1,100,100],[100,1,100],[100,100,1]] |
Verifies optimal path selection |
[[8,16],[19,18],[8,5],[15,9]] |
Exercises multiple DP transitions |
[] |
Defensive empty-input handling |
Edge Cases
One important edge case is a single house. In this situation, there are no adjacency constraints because no neighboring house exists. A buggy implementation might still attempt to reference a previous row or incorrectly enforce color restrictions. This implementation handles the case naturally because the first iteration simply selects the minimum cost among all colors.
Another important edge case is when multiple colors share the same minimum cumulative cost. Incorrect implementations sometimes fail to track the second minimum properly when ties occur. This solution explicitly maintains both the smallest and second smallest cumulative values, ensuring valid transitions even when several colors have identical costs.
A third critical edge case occurs when the cheapest previous color matches the current color. A naive optimization might always reuse the global minimum from the previous row, which would violate the adjacency constraint. This implementation avoids that bug by checking color == prev_min1_color and switching to prev_min2 whenever necessary.
A final edge case is very small color counts, especially k = 2. With only two colors available, the algorithm must alternate carefully between them. Since the implementation explicitly excludes the previous minimum color when necessary, it correctly handles this restrictive configuration without special-case logic.