Skip to main content
Talentd

Paint House - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming4 min readAsked at: Amazon, Microsoft, Uber +5
Practice this problem

Problem Statement

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.

  • For example, 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 == n
  • costs[i].length == 3
  • 1 <= n <= 100
  • 1 <= costs[i][j] <= 20

Approach Overview

Problem 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.

Solution

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(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 DPO(n)O(1)Best general solution when memory usage should be minimal

Video Solution

Paint House (Leetcode) Dynamic Programming | Explained with Code • Pepcoding • 46,510 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Paint House easy or hard?
Paint House is generally considered a medium-level dynamic programming problem. The recurrence relation is straightforward once the state definition is clear, but recognizing the optimal substructure and reducing the DP table to constant space requires some DP experience.
Paint House Python/Java solution
A typical Python or Java solution iterates through the cost matrix and updates three DP values representing the cost of ending with each color. Each update uses the minimum of the other two colors from the previous step. The same logic translates directly across Python, Java, C++, Go, and JavaScript implementations.
How to solve Paint House in O(n)?
Iterate through the houses while maintaining three running costs: the minimum total cost if the previous house was painted red, blue, or green. For the current house, add the paint cost to the minimum of the other two previous colors. Update the three values at each step, producing a linear O(n) dynamic programming solution.
What is the best approach for Paint House?
The best approach is dynamic programming with constant space optimization. Track the minimum cost of painting the previous house with each of the three colors and update the values for the current house. This solution runs in O(n) time and O(1) space and is the approach typically expected in interviews.
Is Paint House asked at Google/Amazon/Meta?
Paint House and its variations appear frequently in interviews at companies like Amazon, Google, and Meta. The problem tests dynamic programming fundamentals such as state definition, transitions, and space optimization. Variants like Paint House II or k-color versions are also common.
What data structure is used in Paint House?
The problem mainly uses arrays and dynamic programming. The input is typically a 2D array representing painting costs, and the algorithm maintains either a DP table or three running variables to store minimum costs for each color choice.
What is the time complexity of Paint House?
The optimal Paint House solution runs in O(n) time, where n is the number of houses. Each house requires constant work to compute the minimum cost using the previous house’s three color values. The space complexity can be reduced to O(1) by storing only the last row of DP values.

Ready to solve this problem?

Practice Paint House with our built-in code editor and test cases.

Practice on FleetCode
Previous

House Robber

Next

House Robber II