Paint House — Solution in Python, Java & C++
Paint House solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Meta.
Paint House is a medium coding problem on arrays and dynamic programming, asked in Amazon, Meta and LinkedIn interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Meta, LinkedIn
- 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 row of n houses must each be painted red, blue or green. costs[i] = [red, blue, green] gives the cost of each colour for house i.
No two adjacent houses may share a colour. Return the minimum total cost.
Example 1
Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Blue, green, blue: 2 + 5 + 3 = 10.
Example 2
Input: costs = [[7,6,2]]
Output: 2
Example 3
Input: costs = [[1,2,3],[1,2,3]]
Output: 3
Explanation: Red then blue: 1 + 2 = 3.
Constraints
1 <= costs.length <= 100costs[i].length == 31 <= costs[i][j] <= 20
Hints for Paint House
Hint 1
Track the best total for each possible colour of the current house.
Hint 2
The cheapest way to end house
iin red iscosts[i][0]plus the cheaper of ending housei-1in blue or green.Hint 3
Three rolling values are enough — no table needed.
How to solve Paint House
The only thing the future needs to know about the past is the colour of the last house, so three running totals capture the whole state.
Approach
- Initialise
r,g,bwith the first house's three costs. - For each later house, compute the new totals: each colour's cost plus the minimum of the other two previous totals.
- Update all three simultaneously — the new values must come from the old ones.
- Return the minimum of the three at the end.
Why it works
The adjacency rule only forbids repeating the immediately previous colour, so the optimal cost of ending at house i in a given colour depends solely on the two other colours at i-1. That is exactly the recurrence.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Overwriting
rbefore computinggandbfeeds the new value back into the same step. - Greedily picking the cheapest colour per house ignores the adjacency constraint and is wrong.
- Note the column order here is [red, blue, green], matching the problem statement.
Reference solution
Python
from typing import List
def minCost(costs: List[List[int]]) -> int:
if not costs:
return 0
r, g, b = costs[0]
for i in range(1, len(costs)):
r, g, b = (
costs[i][0] + min(g, b),
costs[i][1] + min(r, b),
costs[i][2] + min(r, g),
)
return min(r, g, b)Java
public static int minCost(int[][] costs) {
if (costs.length == 0) return 0;
int r = costs[0][0], g = costs[0][1], b = costs[0][2];
for (int i = 1; i < costs.length; i++) {
int nr = costs[i][0] + Math.min(g, b);
int ng = costs[i][1] + Math.min(r, b);
int nb = costs[i][2] + Math.min(r, g);
r = nr; g = ng; b = nb;
}
return Math.min(r, Math.min(g, b));
}C++
int minCost(vector<vector<int>>& costs) {
if (costs.empty()) return 0;
int r = costs[0][0], g = costs[0][1], b = costs[0][2];
for (int i = 1; i < (int) costs.size(); i++) {
int nr = costs[i][0] + min(g, b);
int ng = costs[i][1] + min(r, b);
int nb = costs[i][2] + min(r, g);
r = nr; g = ng; b = nb;
}
return min(r, min(g, b));
}JavaScript
var minCost = function(costs) {
if (costs.length === 0) return 0;
let r = costs[0][0], g = costs[0][1], b = costs[0][2];
for (let i = 1; i < costs.length; i++) {
const nr = costs[i][0] + Math.min(g, b);
const ng = costs[i][1] + Math.min(r, b);
const nb = costs[i][2] + Math.min(r, g);
r = nr; g = ng; b = nb;
}
return Math.min(r, Math.min(g, b));
};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