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.
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.lengthn == cost[i].length1 <= m <= 1001 <= n <= 201 <= target <= m0 <= houses[i] <= n1 <= cost[i][j] <= 104Problem 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.
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.
Python
JavaScript
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with 3D Array | Time Complexity: O(m * target * n^2), as we iterate through every house, neighborhood, and color combination. |
| Memoization with DFS | Time Complexity: O(m * target * n), since each subproblem is solved independently. |
| Dynamic Programming | — |
| Approach | Time | Space | When 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. |
Paint House III • Fraz • 9,833 views views
Watch 9 more video solutions →Practice Paint House III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor