Skip to main content
Talentd

Paint House II - Solution & Explanation

HardPremiumFree on FleetCodeArrayDynamic Programming4 min readAsked at: Meta, LinkedIn
Practice this problem

Problem Statement

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 house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, 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 == n
  • costs[i].length == k
  • 1 <= n <= 100
  • 2 <= k <= 20
  • 1 <= 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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Basic Dynamic ProgrammingO(n * k^2)O(k)Good starting point to understand the recurrence and constraints
Optimized DP with Two MinimumsO(n * k)O(1)Best solution for interviews and large k values

Video Solution

Paint House - 2 (Many Colors) Dynamic Programming | Explained with Code • Pepcoding • 35,069 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Paint Fence

Next

Paint House