Paint House III — Solution in Python, Java & C++
Paint House III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Paint House III is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A street has m houses in a row, and each must be painted one of n colours, labelled 1 to n. Some houses were already painted last summer and must not be repainted.
A neighbourhood is a maximal block of consecutive houses with the same colour. For example, the colours [1,2,2,3,3,2,1,1] form 5 neighbourhoods: {1}, {2,2}, {3,3}, {2}, {1,1}.
You are given houses, where houses[i] is the colour of house i or 0 if it is unpainted; an m x n matrix cost, where cost[i][j] is the price of painting house i with colour j + 1; and an integer target. Return the minimum cost of painting every unpainted house so that the street has exactly target neighbourhoods, or -1 if that is impossible.
Example 1
Input: houses = [0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1]], m = 4, n = 2, target = 2
Output: 13
Explanation: Colours `[1,2,2,2]` (or `[1,1,1,2]`) make two neighbourhoods for 1 + 1 + 10 + 1 = 13.
Example 2
Input: houses = [0,2,1,0], cost = [[4,2],[3,3],[7,1],[2,6]], m = 4, n = 2, target = 3
Output: 6
Explanation: Paint house 0 with colour 1 and house 3 with colour 1: `[1,2,1,1]` has three neighbourhoods.
Example 3
Input: houses = [1,2,1], cost = [[1,1],[1,1],[1,1]], m = 3, n = 2, target = 2
Output: -1
Explanation: Every house is painted already and there are three neighbourhoods.
Constraints
m == houses.length == cost.lengthn == cost[i].length1 <= m <= 1001 <= n <= 201 <= target <= m0 <= houses[i] <= n1 <= cost[i][j] <= 10^4
Hints for Paint House III
Hint 1
Going left to right, a new neighbourhood starts exactly when a house's colour differs from the previous house's colour.
Hint 2
So the state after house
ineeds only two numbers: the colour of houseiand how many neighbourhoods exist so far.Hint 3
dp[c][t]= cheapest cost with the current house colouredcandtneighbourhoods. For the next house and each allowed colourc2(only its fixed colour if already painted), move from everydp[c][t]todp[c2][t + (c != c2)], adding the paint cost (0 for a painted house).
How to solve Paint House III
Whether house i starts a new neighbourhood depends only on its colour and the colour of house i - 1. So a DP over houses whose state is (colour of the current house, neighbourhoods so far) captures everything the future needs.
Approach
- Let
dp[c][t]be the minimum cost to paint houses0..iwith houseicolouredcand exactlytneighbourhoods; start from house 0 witht = 1for each allowed colour. - For each next house
iand each allowed colourc2(every colour ifhouses[i] == 0, otherwise onlyhouses[i]), with paint costp(0 if already painted): - for every previous colour
cand counttwith a finitedp[c][t], sett2 = tifc == c2elset + 1; ift2 <= target, relaxnext[c2][t2]withdp[c][t] + p. - After the last house, the answer is the minimum of
dp[c][target]over all colours, or-1if every entry is infinite.
Why it works
Two partial paintings of houses 0..i that agree on the last colour and the neighbourhood count are interchangeable for everything that follows: the future cost and the future neighbourhood changes depend on nothing else. Keeping only the cheapest one per state is therefore safe, and the transitions enumerate every colour choice for the next house.
Complexity
- Time —
O(m · n^2 · target) - Space —
O(n · target)
Pitfalls
- Painted houses keep their colour and cost nothing — but they still count towards neighbourhoods.
- Discard states whose count exceeds
target; they can never come back down. - Return
-1when no state reaches exactlytarget, rather than an infinity sentinel.
Reference solution
Python
from typing import List
def minCost(houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
INF = float('inf')
dp = [[INF] * (target + 1) for _ in range(n + 1)]
for c in range(1, n + 1):
if houses[0] == 0:
dp[c][1] = cost[0][c - 1]
elif houses[0] == c:
dp[c][1] = 0
for i in range(1, m):
nd = [[INF] * (target + 1) for _ in range(n + 1)]
for c in range(1, n + 1):
if houses[i] != 0 and houses[i] != c:
continue
paint = 0 if houses[i] else cost[i][c - 1]
for pc in range(1, n + 1):
row = dp[pc]
for t in range(1, target + 1):
if row[t] == INF:
continue
nt = t if pc == c else t + 1
if nt <= target and row[t] + paint < nd[c][nt]:
nd[c][nt] = row[t] + paint
dp = nd
best = min(dp[c][target] for c in range(1, n + 1))
return -1 if best == INF else bestJava
public static int minCost(int[] houses, int[][] cost, int m, int n, int target) {
final int INF = Integer.MAX_VALUE / 2;
int[][] dp = new int[n + 1][target + 1];
for (int[] row : dp) Arrays.fill(row, INF);
for (int c = 1; c <= n; c++) {
if (houses[0] == 0) dp[c][1] = cost[0][c - 1];
else if (houses[0] == c) dp[c][1] = 0;
}
for (int i = 1; i < m; i++) {
int[][] nd = new int[n + 1][target + 1];
for (int[] row : nd) Arrays.fill(row, INF);
for (int c = 1; c <= n; c++) {
if (houses[i] != 0 && houses[i] != c) continue;
int paint = houses[i] != 0 ? 0 : cost[i][c - 1];
for (int pc = 1; pc <= n; pc++) {
for (int t = 1; t <= target; t++) {
if (dp[pc][t] == INF) continue;
int nt = pc == c ? t : t + 1;
if (nt <= target && dp[pc][t] + paint < nd[c][nt]) nd[c][nt] = dp[pc][t] + paint;
}
}
}
dp = nd;
}
int best = INF;
for (int c = 1; c <= n; c++) best = Math.min(best, dp[c][target]);
return best == INF ? -1 : best;
}C++
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
const int INF = INT_MAX / 2;
vector<vector<int>> dp(n + 1, vector<int>(target + 1, INF));
for (int c = 1; c <= n; c++) {
if (houses[0] == 0) dp[c][1] = cost[0][c - 1];
else if (houses[0] == c) dp[c][1] = 0;
}
for (int i = 1; i < m; i++) {
vector<vector<int>> nd(n + 1, vector<int>(target + 1, INF));
for (int c = 1; c <= n; c++) {
if (houses[i] != 0 && houses[i] != c) continue;
int paint = houses[i] != 0 ? 0 : cost[i][c - 1];
for (int pc = 1; pc <= n; pc++) {
for (int t = 1; t <= target; t++) {
if (dp[pc][t] == INF) continue;
int nt = pc == c ? t : t + 1;
if (nt <= target && dp[pc][t] + paint < nd[c][nt]) nd[c][nt] = dp[pc][t] + paint;
}
}
}
dp = nd;
}
int best = INF;
for (int c = 1; c <= n; c++) best = min(best, dp[c][target]);
return best == INF ? -1 : best;
}JavaScript
var minCost = function(houses, cost, m, n, target) {
var INF = Infinity;
var fresh = function() {
var t = [];
for (var c = 0; c <= n; c++) t.push(new Array(target + 1).fill(INF));
return t;
};
var dp = fresh();
for (var c = 1; c <= n; c++) {
if (houses[0] === 0) dp[c][1] = cost[0][c - 1];
else if (houses[0] === c) dp[c][1] = 0;
}
for (var i = 1; i < m; i++) {
var nd = fresh();
for (var c = 1; c <= n; c++) {
if (houses[i] !== 0 && houses[i] !== c) continue;
var paint = houses[i] ? 0 : cost[i][c - 1];
for (var pc = 1; pc <= n; pc++) {
for (var t = 1; t <= target; t++) {
if (dp[pc][t] === INF) continue;
var nt = pc === c ? t : t + 1;
if (nt <= target && dp[pc][t] + paint < nd[c][nt]) nd[c][nt] = dp[pc][t] + paint;
}
}
}
dp = nd;
}
var best = INF;
for (var c = 1; c <= n; c++) best = Math.min(best, dp[c][target]);
return best === INF ? -1 : best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming