Paint House II solution and explanation
9 more videos on this problem
LeetCode Python 265 Paint House IINan Liu · 9:01 · 825 views
265. Paint House II - Week 3/5 Leetcode May ChallengeProgramming Live with Larry · 6:57 · 719 views
Live meetup June 11, 2020 -Dynamic Programming- Paint House II, III problems (leetcode 265, 1473)interviewBoost · 1:46:35 · 483 views
Leetcode 265. Paint House II (2d dp)LetsCode · 3:46 · 472 views
265. Paint House II - Week 5/5 Leetcode October ChallengeProgramming Live with Larry · 9:30 · 360 views
Paint House II 2Happy Coding · 8:17 · 283 views
LeetCode in Python 265. Paint House II (Hard) ｜动态规划DP终极学习计划！- Day 3 (2/3) -MichelleMichelle小梦想家 · 23:42 · 207 views
Another Dynamic Programming Tutorial using Leetcode 265 and 256Emerald Bay · 5:34 · 119 views
Paint House II 1Happy Coding · 14:41 · 117 views
Paint House - 2 (Many Colors) Dynamic Programming | Explained with CodePepcoding · 31:19 · 35K views
The problem
There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by an n x k cost matrix costs.
- For example,
costs[0][0]is the cost of painting house0with color0;costs[1][2]is the cost of painting house1with color2, and so on...
Return the minimum cost to paint all houses.
Example 1:
Input: costs = [[1,5,3],[2,9,4]] Output: 5 Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.
Example 2:
Input: costs = [[1,3],[2,4]] Output: 5
Constraints:
costs.length == ncosts[i].length == k1 <= n <= 1002 <= k <= 201 <= costs[i][j] <= 20
Follow up: Could you solve it in O(nk) runtime?
Approach overview
Problem Overview: You are given n houses and k colors. Each costs[i][j] represents the cost of painting house i with color j. Adjacent houses cannot share the same color. The goal is to compute the minimum total cost to paint all houses while respecting this constraint.
Approach 1: Basic Dynamic Programming (O(n * k^2) time, O(k) space)
This approach builds the solution house by house using dynamic programming. For each house i and color j, you compute the cost as costs[i][j] + min(previous costs of all colors except j). That means iterating through all k colors from the previous row to find the minimum valid value. The DP state only needs the previous row, so space can be reduced to O(k). The downside is the nested scan over colors, giving O(n * k^2) time.
Approach 2: Optimized Dynamic Programming with Two Minimums (O(n * k) time, O(1) extra space)
The bottleneck in the previous approach is repeatedly searching for the minimum cost among k colors excluding the current one. Instead, track the smallest and second smallest values from the previous row. If the current color is different from the index of the smallest cost, use that value. Otherwise use the second smallest. This removes the inner loop and reduces each transition to constant time. You iterate through each house and each color once, resulting in O(n * k) time and O(1) extra space beyond the input.
The optimization works because every color only needs to know whether it conflicts with the global minimum from the previous step. If it conflicts, the second minimum is the next valid choice. This pattern appears frequently in array-based DP problems where transitions exclude a single index.
Recommended for interviews: Interviewers expect the optimized DP with two minimums. Starting with the O(n * k^2) dynamic programming formulation shows you understand the recurrence. Converting it to the O(n * k) solution demonstrates optimization skills and familiarity with dynamic programming state transitions. Most production-quality solutions use the optimized approach.
Solution
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n, k = len(costs), len(costs[0])
f = costs[0][:]
for i in range(1, n):
g = costs[i][:]
for j in range(k):
t = min(f[h] for h in range(k) if h != j)
g[j] += t
f = g
return min(f)class Solution {
public int minCostII(int[][] costs) {
int n = costs.length, k = costs[0].length;
int[] f = costs[0].clone();
for (int i = 1; i < n; ++i) {
int[] g = costs[i].clone();
for (int j = 0; j < k; ++j) {
int t = Integer.MAX_VALUE;
for (int h = 0; h < k; ++h) {
if (h != j) {
t = Math.min(t, f[h]);
}
}
g[j] += t;
}
f = g;
}
return Arrays.stream(f).min().getAsInt();
}
}class Solution {
public:
int minCostII(vector<vector<int>>& costs) {
int n = costs.size(), k = costs[0].size();
vector<int> f = costs[0];
for (int i = 1; i < n; ++i) {
vector<int> g = costs[i];
for (int j = 0; j < k; ++j) {
int t = INT_MAX;
for (int h = 0; h < k; ++h) {
if (h != j) {
t = min(t, f[h]);
}
}
g[j] += t;
}
f = move(g);
}
return *min_element(f.begin(), f.end());
}
};func minCostII(costs [][]int) int {
n, k := len(costs), len(costs[0])
f := cp(costs[0])
for i := 1; i < n; i++ {
g := cp(costs[i])
for j := 0; j < k; j++ {
t := math.MaxInt32
for h := 0; h < k; h++ {
if h != j && t > f[h] {
t = f[h]
}
}
g[j] += t
}
f = g
}
return slices.Min(f)
}
func cp(arr []int) []int {
t := make([]int, len(arr))
copy(t, arr)
return t
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Dynamic Programming | O(n * k^2) | O(k) | Good starting point to understand the recurrence and constraints |
| Optimized DP with Two Minimums | O(n * k) | O(1) | Best solution for interviews and large k values |
Frequently asked questions
Is Paint House II easy or hard?
Paint House II is categorized as a Hard problem because the straightforward dynamic programming approach is O(n * k^2). Recognizing how to optimize it to O(n * k) by tracking the two minimum costs requires deeper understanding of DP transitions.
How to solve Paint House II in O(n)?
The problem cannot generally be solved in strict O(n) because each house has k color options that must be considered. The optimal approach achieves O(n * k) time by keeping track of the minimum and second minimum painting costs from the previous house and using them to update the current row in constant time.
Paint House II Python or Java solution?
Implementations in Python, Java, C++, and Go follow the same optimized DP logic. Iterate through houses, track the smallest and second smallest costs from the previous row, and update each color cost accordingly to maintain O(n * k) complexity.
What is the best approach for Paint House II?
The best approach uses dynamic programming with tracking of the smallest and second smallest costs from the previous row. This avoids scanning all colors for every state transition. The result runs in O(n * k) time and O(1) extra space, which is optimal for this problem.
What data structure is used in Paint House II?
The solution primarily uses arrays to store painting costs and dynamic programming states. During optimization, two variables track the smallest and second smallest costs from the previous house to speed up transitions.
What is the time complexity of Paint House II?
The optimal solution runs in O(n * k) time where n is the number of houses and k is the number of colors. Each house and color combination is processed once while maintaining the smallest and second smallest values from the previous step.
Is Paint House II asked at Google, Amazon, or Meta?
Paint House II is a common dynamic programming interview problem and variations of it appear at companies like Amazon, Google, and Meta. It tests DP state design and optimization techniques such as tracking minimum values across transitions.