There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. 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 3 cost matrix costs.
costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...Return the minimum cost to paint all houses.
Example 1:
Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.
Example 2:
Input: costs = [[7,6,2]] Output: 2
Constraints:
costs.length == ncosts[i].length == 31 <= n <= 1001 <= costs[i][j] <= 20Problem Overview: You’re given n houses and 3 paint colors. Each house has a cost for each color. Adjacent houses cannot use the same color. The goal is to compute the minimum total cost to paint all houses while respecting this constraint.
Approach 1: Brute Force Recursion (O(2^n) time, O(n) space)
Try every valid color combination while ensuring the current house uses a different color from the previous one. For each house, recursively choose among the remaining two colors and accumulate the cost. This builds a decision tree with roughly two choices per level, producing exponential time complexity. The recursion stack requires O(n) space. This approach demonstrates the core constraint but becomes impractical as n grows.
Approach 2: Dynamic Programming (Tabulation) (O(n) time, O(n) space)
The key observation: the cheapest way to paint house i with color c depends only on the minimum cost of painting house i-1 with the other two colors. Define dp[i][c] as the minimum cost up to house i if it’s painted color c. Transition: dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]), and similarly for the other colors. Iterate through the houses once and fill the table. This converts the exponential search into linear time. This approach relies on dynamic programming and simple array traversal.
Approach 3: Space Optimized Dynamic Programming (O(n) time, O(1) space)
Only the previous house’s three costs are needed to compute the current house. Instead of storing the entire DP table, track three variables representing the minimum cost ending with each color for the previous house. For every new house, compute the new values using the same transition formula, then overwrite the previous values. This keeps the algorithm linear while reducing memory usage to constant space. This is the most common production implementation.
Recommended for interviews: The space‑optimized dynamic programming approach. It demonstrates that you recognize the overlapping subproblem structure and can reduce both time and memory usage. Explaining the brute force recursion first shows understanding of the constraint, while deriving the DP transition proves strong problem‑solving skills.
Python
Java
C++
Go
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^n) | O(n) | Conceptual understanding of constraints and exploring all valid color choices |
| Dynamic Programming (Tabulation) | O(n) | O(n) | Clear DP formulation when explaining transitions step by step |
| Space Optimized DP | O(n) | O(1) | Best general solution when memory usage should be minimal |
Paint House (Leetcode) Dynamic Programming | Explained with Code • Pepcoding • 46,029 views views
Watch 9 more video solutions →Practice Paint House with our built-in code editor and test cases.
Practice on FleetCode