Skip to main content
Talentd

Paint House III - Solution & Explanation

HardArrayDynamic Programming20 min readAsked at: PayPal, Google, LinkedIn
Practice this problem

Problem Statement

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color.

  • For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}].

Given an array houses, an m x n matrix cost and an integer target where:

  • houses[i]: is the color of the house i, and 0 if the house is not painted yet.
  • cost[i][j]: is the cost of paint the house i with the color j + 1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.

 

Example 1:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2:

Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:

Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

 

Constraints:

  • m == houses.length == cost.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 104

Approach Overview

Problem Overview: You are given m houses and n colors. Some houses are already painted while others must be painted with a cost matrix. The goal is to minimize total painting cost while forming exactly target neighborhoods, where a neighborhood is a contiguous group of houses with the same color.

Approach 1: Memoization with DFS (Top‑Down DP) (Time: O(m * n^2 * target), Space: O(m * n * target))

This approach models the problem as a recursive decision process. At each house index you decide which color to paint. The state is defined by (index, prevColor, neighborhoods). If the current color differs from the previous one, the neighborhood count increases. Use DFS to explore painting choices and store results in a memo table so repeated states are computed once. When a house is already painted, the recursion simply continues with that color. This approach is easier to reason about because it mirrors the decision tree directly while memoization ensures the complexity stays manageable.

Approach 2: Dynamic Programming with 3D Array (Bottom‑Up) (Time: O(m * n^2 * target), Space: O(m * n * target))

The bottom‑up DP builds solutions iteratively. Define dp[i][c][k] as the minimum cost to paint houses up to index i, where house i has color c and exactly k neighborhoods have been formed. For each house, iterate through all possible colors and transition from every previous color. If the color changes, increment the neighborhood count; otherwise keep it the same. When a house is already painted, only that color is considered. The final answer is the minimum cost among dp[m-1][color][target]. This approach is deterministic and avoids recursion overhead, making it common in competitive programming solutions involving dynamic programming and multidimensional state transitions.

Both solutions rely heavily on tracking state transitions across houses, colors, and neighborhood counts. The cost matrix and house constraints are stored in simple arrays, while the optimization logic is handled through DP states built on top of arrays and cached subproblems.

Recommended for interviews: The bottom‑up 3D DP solution is typically what interviewers expect for this problem. It clearly shows how you design a DP state and manage transitions across multiple constraints. The memoized DFS version is still valuable during interviews because it demonstrates how you convert an exponential search into polynomial time using caching.

Approach 1: Dynamic Programming with 3D Array

In this approach, we use a 3-dimensional dynamic programming table where dp[i][j][k] represents the minimum cost to paint up to the i-th house with j neighborhoods using color k on the i-th house. The goal is to fill this table and find the minimum value for the last house and target neighborhoods.

This Python function calculates the minimum cost to paint houses while forming the target number of neighborhoods. The solution involves iterating through each house and possible neighborhood configurations, adjusting costs based on whether a house is pre-painted or not.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(m * target * n^2), as we iterate through every house, neighborhood, and color combination.
Space Complexity: O(m * target * n), for storing the dynamic programming table.

Try this approach in the editor →

Approach 2: Memoization with DFS

This approach applies memoization with a depth-first search (DFS) method to explore potential painting configurations. We recursively search for the minimum cost pathway to achieve the target neighborhood using memoized results to reduce redundant calculations.

This Java solution uses recursion with memoization to explore possible house coloring choices that achieve the target neighborhood count with minimum cost. The results of subproblems are stored in a memoization table to efficiently compute the overall result.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(m * target * n), since each subproblem is solved independently.
Space Complexity: O(m * target * n), for the memoization table to store intermediate results.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j][k] to represent the minimum cost to paint houses from index 0 to i, with the last house painted in color j, and exactly forming k blocks. The answer is f[m-1][j][target], where j ranges from 1 to n. Initially, we check if the house at index 0 is already painted. If it is not painted, then f[0][j][1] = cost[0][j - 1], where j \in [1,..n]. If it is already painted, then f[0][houses[0]][1] = 0. All other values of f[i][j][k] are initialized to infty.

Next, we start iterating from index i=1. For each i, we check if the house at index i is already painted:

If it is not painted, we can paint the house at index i with color j. We enumerate the number of blocks k, where k \in [1,..min(target, i + 1)], and enumerate the color of the previous house j_0, where j_0 \in [1,..n]. Then we can derive the state transition equation:

$ f[i][j][k] = min_{j_0 \in [1,..n]} { f[i - 1][j_0][k - (j neq j_0)] + cost[i][j - 1] }

If it is already painted, we can paint the house at index i with color j. We enumerate the number of blocks k, where k \in [1,..min(target, i + 1)], and enumerate the color of the previous house j_0, where j_0 \in [1,..n]. Then we can derive the state transition equation:

f[i][j][k] = min_{j_0 \in [1,..n]} { f[i - 1][j_0][k - (j neq j_0)] }

Finally, we return f[m - 1][j][target], where j \in [1,..n]. If all values of f[m - 1][j][target] are infty, then return -1.

The time complexity is O(m times n^2 times target), and the space complexity is O(m times n times target). Here, m, n, and target$ represent the number of houses, the number of colors, and the number of blocks, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with 3D Array

Time Complexity: O(m * target * n^2), as we iterate through every house, neighborhood, and color combination.
Space Complexity: O(m * target * n), for storing the dynamic programming table.

Memoization with DFS

Time Complexity: O(m * target * n), since each subproblem is solved independently.
Space Complexity: O(m * target * n), for the memoization table to store intermediate results.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Memoization with DFS (Top‑Down DP)O(m * n^2 * target)O(m * n * target)When you want a natural recursive formulation and easier reasoning about decisions.
Dynamic Programming with 3D Array (Bottom‑Up)O(m * n^2 * target)O(m * n * target)Preferred in interviews and competitive programming for deterministic iteration and no recursion overhead.

Video Solution

Paint House III • Fraz • 9,909 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Paint House III easy or hard?
Paint House III is classified as a Hard problem on LeetCode. The difficulty comes from designing a DP state that tracks house index, current color, and the number of neighborhoods simultaneously while minimizing cost.
Paint House III Python/Java solution
Python and Java implementations usually follow the same DP formulation. Python solutions often use recursion with memoization decorators, while Java solutions commonly implement DFS with a HashMap cache or a bottom‑up 3D DP array.
How to solve Paint House III in O(n)?
Paint House III cannot be solved in strict O(n) time because each house may require checking multiple color transitions and neighborhood counts. The optimal solution uses dynamic programming with complexity O(m * n^2 * target). The additional dimensions are necessary to track both color changes and neighborhood formation.
What is the best approach for Paint House III?
The standard solution uses dynamic programming with a 3D state dp[i][color][k], representing the minimum cost to paint up to house i with a given color and k neighborhoods. Each transition checks whether the color changed from the previous house. This approach runs in O(m * n^2 * target) time and O(m * n * target) space.
Is Paint House III asked at Google/Amazon/Meta?
Paint House III represents a class of dynamic programming problems frequently asked in interviews at companies like Google, Amazon, and Meta. Variants of the Paint House problem appear often because they test multidimensional DP state design and transition logic.
What data structure is used in Paint House III?
The main data structures are arrays and dynamic programming tables. Solutions typically use a 3D DP array or a memoization map keyed by (houseIndex, previousColor, neighborhoods). These structures efficiently store intermediate results and avoid recomputation.
What is the time complexity of Paint House III?
The optimal dynamic programming solution runs in O(m * n^2 * target) time. For each house, the algorithm iterates through all possible current colors and all previous colors while tracking neighborhood counts. Space complexity is O(m * n * target) for the DP table or memo cache.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Number of Distinct Roll Sequences

Next

Paint House IV