Paint House II
Hard · 1-D Dynamic Programming · Explanation and code example
Dynamic programming with Optimized Time and Space
How it works
Building on the previous optimization, we realize we do not actually need to store the entire previous row. We only need three pieces of information: the minimum cost, the second minimum cost, and which color achieved the minimum.
By tracking just these three values as we process each house, we can compute everything in O(1) space while maintaining O(n * k) time complexity.
Steps
- Initialize by finding the minimum cost, second minimum cost, and minimum color index from the first row.
- For each subsequent house, iterate through all colors:
- If the current color equals the previous minimum color, the cost is
current_cost + prev_second_min. - Otherwise, the cost is
current_cost + prev_min.
- If the current color equals the previous minimum color, the cost is
- Track the new minimum, second minimum, and minimum color as you process each color.
- After processing all houses, the final minimum cost is the answer.
Complexity
-
Time complexity:
O(n × k) -
Space complexity:
O(1)
Where
nis the number of houses in a row, andkis the number of colors available for painting.
Things to watch for
Using O(k^2) Time Per House Without Optimization
The naive approach of checking all k colors from the previous row for each of k colors in the current row results in O(n*k^2) time. For large k values, this times out. The key insight is that you only need to track the minimum and second minimum costs from the previous row, reducing per-house work to O(k).
Not Handling the Case When k Equals 1
When there is only one color available, it is impossible to paint more than one house without violating the adjacent color constraint. Some implementations crash or return incorrect results because they assume k >= 2. Always check if k equals 1 and n > 1, returning an error indicator or handling it appropriately.
Forgetting to Track Which Color Achieved the Minimum
When optimizing with minimum and second minimum tracking, you must remember which color index gave the minimum cost. Without this, you cannot determine whether to use the minimum or second minimum when processing the next row, since you need the second minimum only when the current color matches the previous minimum color.
Modifying the Input Array Unexpectedly
Some solutions modify the costs array in place to save space. While this works, it can cause issues if the caller expects the original data to remain unchanged. Either document this behavior clearly, work on a copy of the input, or use the O(1) space solution that tracks only the necessary values without modifying input.
Off-by-One Errors in House Indexing
The DP processes houses from index 1 to n-1, using costs from house 0 as the base case. Confusing 0-indexed and 1-indexed loops, or incorrectly referencing costs[house-1] versus costs[house], leads to accessing wrong cost values or array out-of-bounds errors.
Python code example
from typing import List
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n = len(costs)
if n == 0: return 0 # This is a valid case.
k = len(costs[0])
# Firstly, we need to determine the 2 lowest costs of
# the first row. We also need to remember the color of
# the lowest.
prev_min_cost = prev_second_min_cost = prev_min_color = None
for color, cost in enumerate(costs[0]):
if prev_min_cost is None or cost < prev_min_cost:
prev_second_min_cost = prev_min_cost
prev_min_color = color
prev_min_cost = cost
elif prev_second_min_cost is None or cost < prev_second_min_cost:
prev_second_min_cost = cost
# And now, we need to work our way down, keeping track of the minimums.
for house in range(1, n):
min_cost = second_min_cost = min_color = None
for color in range(k):
# Determime cost for this cell (without writing it into input array.)
cost = costs[house][color]
if color == prev_min_color:
cost += prev_second_min_cost
else:
cost += prev_min_cost
# And work out whether or not it is a current minimum.
if min_cost is None or cost < min_cost:
second_min_cost = min_cost
min_color = color
min_cost = cost
elif second_min_cost is None or cost < second_min_cost:
second_min_cost = cost
# Transfer currents to be prevs.
prev_min_cost = min_cost
prev_min_color = min_color
prev_second_min_cost = second_min_cost
return prev_min_cost
C++ code example
class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
if (costs.empty()) return 0;
int k = costs[0].size();
int n = costs.size();
int prevMin = -1, prevSecondMin = -1, prevMinColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[0][color];
if (prevMin == -1 || cost < prevMin) {
prevSecondMin = prevMin;
prevMinColor = color;
prevMin = cost;
} else if (prevSecondMin == -1 || cost < prevSecondMin) {
prevSecondMin = cost;
}
}
for (int house = 1; house < n; house++) {
int minCost = -1, secondMin = -1, minColor = -1;
for (int color = 0; color < k; color++) {
int cost = costs[house][color];
if (color == prevMinColor) {
cost += prevSecondMin;
} else {
cost += prevMin;
}
if (minCost == -1 || cost < minCost) {
secondMin = minCost;
minColor = color;
minCost = cost;
} else if (secondMin == -1 || cost < secondMin) {
secondMin = cost;
}
}
prevMin = minCost;
prevSecondMin = secondMin;
prevMinColor = minColor;
}
return prevMin;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.