Paint House III

Hard

#1360Time: O(m * target * n^2) The number of states is `m * target * n`. For each state, if the house is not painted, we iterate through `n` colors, leading to the `n^2` factor. If all houses are painted, the complexity would be closer to `O(m * target * n)`.Space: O(m * target * n) This is for the memoization table `memo` of size `m x (target+1) x (n+1)`. The recursion depth adds an additional O(m) to the space complexity, which is dominated by the memoization table.1 company

Patterns

Dynamic Programming

Data structures

Array

Companies

PayPal

Prompt

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] <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses recursion with memoization, a top-down dynamic programming technique. We define a recursive function that explores all possible ways to paint the houses while keeping track of the current house index, the number of neighborhoods formed so far, and the color of the previous house. Memoization is used to store the results of subproblems to avoid redundant calculations, which is crucial for passing the time limits.

Algorithm

The core of this approach is a recursive function, let's call it solve(houseIndex, neighborhoodCount, prevColor), which calculates the minimum cost.
The parameters of this function are:
- houseIndex: The index of the house we are currently considering to paint (from 0 to m-1).
- neighborhoodCount: The number of neighborhoods formed so far, up to houseIndex - 1.
- prevColor: The color of the previous house (houseIndex - 1). We can use 0 as a virtual color for the house before the first one.
Base Cases:
- If neighborhoodCount exceeds target, it's an invalid path, so we return a very large value (infinity).
- If houseIndex reaches m (all houses considered), we check if neighborhoodCount is exactly target. If it is, we've found a valid painting scheme, and the cost for the remaining (none) houses is 0. Otherwise, it's an invalid scheme, so we return infinity.
Recursive Step:
- If the current house houses[houseIndex] is already painted, we must use its color. We determine if this forms a new neighborhood by comparing its color to prevColor and recurse for the next house: solve(houseIndex + 1, newNeighborhoodCount, houses[houseIndex]).
- If the house is not painted (houses[houseIndex] == 0), we try painting it with every possible color from 1 to n. For each color, we calculate the painting cost and the new neighborhood count, then recursively call the function for the next house. We take the minimum cost among all color choices.
Memoization:
- To avoid recomputing results for the same state (houseIndex, neighborhoodCount, prevColor), we use a 3D array memo to store the results. Before computing, we check if the result is already in memo. After computing, we store the result in memo.

Walkthrough

The state of our recursive function can be defined as solve(houseIndex, neighborhoodCount, prevColor). This function will return the minimum cost to paint houses from houseIndex to m-1, given that we have already formed neighborhoodCount neighborhoods in the prefix 0...houseIndex-1, and the house at houseIndex-1 was painted with prevColor.

When we are at houseIndex, we decide which color to paint it.

If houses[houseIndex] is not 0, its color is fixed. We calculate the new neighborhood count. If the current house color is the same as prevColor, the count doesn't change. Otherwise, it increases by one. We then make a recursive call for houseIndex + 1.
If houses[houseIndex] is 0, we must try all n colors. For each color c, we calculate the cost (cost[houseIndex][c-1]) and the new neighborhood count, and make a recursive call. The minimum cost over all n choices is the result for the current state.

The base cases for the recursion are when we have processed all houses (houseIndex == m) or when the neighborhood count exceeds the target. A 3D memoization table memo[m][target+1][n+1] stores the results to prevent re-computation of the same state.

1class Solution {2    private int m, n, target;3    private int[] houses;4    private int[][] cost;5    private Integer[][][] memo;6    private final int MAX_COST = 1_000_001; // A value larger than max possible cost7 8    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {9        this.houses = houses;10        this.cost = cost;11        this.m = m;12        this.n = n;13        this.target = target;14        // memo[houseIndex][neighborhoods][prevColor]15        this.memo = new Integer[m][target + 1][n + 1];16 17        int result = solve(0, 0, 0); // index, neighborhoods formed, prev_color18 19        return result >= MAX_COST ? -1 : result;20    }21 22    private int solve(int houseIndex, int neighborhoodCount, int prevColor) {23        if (neighborhoodCount > target) {24            return MAX_COST;25        }26        if (houseIndex == m) {27            return neighborhoodCount == target ? 0 : MAX_COST;28        }29 30        if (memo[houseIndex][neighborhoodCount][prevColor] != null) {31            return memo[houseIndex][neighborhoodCount][prevColor];32        }33 34        int minCost = MAX_COST;35 36        if (houses[houseIndex] != 0) { // House is already painted37            int currentColor = houses[houseIndex];38            int newNeighborhoodCount = neighborhoodCount + (currentColor == prevColor ? 0 : 1);39            minCost = solve(houseIndex + 1, newNeighborhoodCount, currentColor);40        } else { // House is not painted, try all colors41            for (int currentColor = 1; currentColor <= n; currentColor++) {42                int newNeighborhoodCount = neighborhoodCount + (currentColor == prevColor ? 0 : 1);43                int currentCost = cost[houseIndex][currentColor - 1] + solve(houseIndex + 1, newNeighborhoodCount, currentColor);44                minCost = Math.min(minCost, currentCost);45            }46        }47 48        return memo[houseIndex][neighborhoodCount][prevColor] = minCost;49    }50}

Complexity

Time

O(m * target * n^2) The number of states is `m * target * n`. For each state, if the house is not painted, we iterate through `n` colors, leading to the `n^2` factor. If all houses are painted, the complexity would be closer to `O(m * target * n)`.

Space

O(m * target * n) This is for the memoization table `memo` of size `m x (target+1) x (n+1)`. The recursion depth adds an additional O(m) to the space complexity, which is dominated by the memoization table.

Trade-offs

Pros

Relatively intuitive to formulate from the problem description.
It naturally prunes the search space by only exploring reachable states.

Cons

The time complexity of O(m * target * n^2) can be slow if n is large.
The space complexity of O(m * target * n) can be large.
Deep recursion could potentially lead to stack overflow for very large m, though not an issue with the given constraints.

A more efficient solution uses bottom-up dynamic programming. The key idea is to build the solution iteratively, from the first house to the last. We can define a DP state dp[i][k][p] as the minimum cost to paint the first i houses, forming exactly k neighborhoods, with the i-th house painted in color p. The crucial observation is that the transition from house i-1 to i involves an O(n) lookup, which can be optimized to O(1) by pre-calculating the two minimum costs from the previous state. Furthermore, we can optimize space because computing the DP values for house i only requires the values from house i-1.

Algorithm

Define a DP table dp[k][p] which stores the minimum cost to paint the houses up to the current one (say, i-1), forming k neighborhoods, with the last house i-1 painted in color p.
Since the calculation for house i only depends on the results for house i-1, we can optimize space by using only two 2D arrays: dp for the current house i and prev_dp for the previous house i-1.
Initialization: Before processing any houses (a virtual state at i=0), the cost is 0 to have 0 neighborhoods. So, prev_dp[0][any_color] = 0, and all other entries are infinity.
Iteration: We iterate through each house i from 1 to m.
- For each house, we compute the new dp table.
- We iterate through the number of neighborhoods k from 1 to target.
- To optimize the transition, for each k, we first find the two minimum costs from the previous state with k-1 neighborhoods (prev_dp[k-1]). Let these be min1 (with color color1) and min2. This takes O(n) time.
- Then, we iterate through each possible color p for the current house i-1.
- The cost to paint the current house with color p is paint_cost.
- The total cost is paint_cost plus the minimum cost from the previous house. This previous cost is the minimum of two cases:
  1. The previous house had the same color p: prev_dp[k][p].
  2. The previous house had a different color (forming a new neighborhood): This requires finding the minimum of prev_dp[k-1] over all colors except p. This is where our pre-calculated min1 and min2 come in handy. The cost is min1 if p is not color1, otherwise it's min2.
- We update dp[k][p] with this minimum total cost.
After iterating through all houses, the answer is the minimum value in dp[target] across all colors.

Walkthrough

This approach builds the solution from the ground up. We use a 2D DP array dp[k][p] to store the minimum cost for the current house, where k is the number of neighborhoods and p is the color of this house. We iterate through each house from i = 1 to m.

For each house i, we calculate its dp table based on the prev_dp table (from house i-1). For each target neighborhood count k and each color p:

The cost to paint house i-1 with color p is paint_cost. This is cost[i-1][p-1] if the house is unpainted, 0 if it's already painted with p, and infinity otherwise.

The total cost dp[k][p] is paint_cost plus the minimum cost from the previous state. This previous cost is derived from two possibilities:

Extending a neighborhood: The previous house (i-2) was also painted with color p. The cost is inherited from prev_dp[k][p]. The number of neighborhoods remains k.
Starting a new neighborhood: The previous house (i-2) had a different color. This means we had k-1 neighborhoods up to house i-2. We need the minimum cost to achieve this, which is min(prev_dp[k-1]).

To make the second case efficient, instead of re-calculating min(prev_dp[k-1]) for each p, we pre-compute the two smallest values in the prev_dp[k-1] row. This reduces the transition from O(n) to O(1), bringing the total time complexity down.

After iterating through all m houses, the minimum value in the dp[target] row is our answer. If this value is still infinity, no solution exists.

1class Solution {2    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {3        final int MAX_COST = 1_000_001;4        5        // dp[k][p] = min cost for houses processed so far, with k neighborhoods, last house color p6        int[][] dp = new int[target + 1][n + 1];7        for (int[] row : dp) {8            java.util.Arrays.fill(row, MAX_COST);9        }10        11        // Base case: before painting any house (i=0), 0 cost for 0 neighborhoods.12        // Any "previous color" is valid for this virtual state.13        for (int p = 0; p <= n; p++) {14            dp[0][p] = 0;15        }16 17        for (int i = 1; i <= m; i++) {18            int houseIdx = i - 1;19            int[][] next_dp = new int[target + 1][n + 1];20            for (int[] row : next_dp) {21                java.util.Arrays.fill(row, MAX_COST);22            }23 24            for (int k = 1; k <= target && k <= i; k++) {25                // Find the two cheapest colors for the previous state with k-1 neighborhoods26                int min1 = MAX_COST, color1 = -1;27                int min2 = MAX_COST;28                for (int p_prev = 1; p_prev <= n; p_prev++) {29                    if (dp[k - 1][p_prev] < min1) {30                        min2 = min1;31                        min1 = dp[k - 1][p_prev];32                        color1 = p_prev;33                    } else if (dp[k - 1][p_prev] < min2) {34                        min2 = dp[k - 1][p_prev];35                    }36                }37 38                for (int p = 1; p <= n; p++) {39                    if (houses[houseIdx] != 0 && houses[houseIdx] != p) {40                        continue;41                    }42 43                    int paintCost = (houses[houseIdx] == 0) ? cost[houseIdx][p - 1] : 0;44                    45                    // Case 1: Extend the current neighborhood46                    int cost1 = dp[k][p];47 48                    // Case 2: Start a new neighborhood49                    int cost2 = (p == color1) ? min2 : min1;50                    51                    int totalCost = paintCost + Math.min(cost1, cost2);52                    if (totalCost < MAX_COST) {53                        next_dp[k][p] = totalCost;54                    }55                }56            }57            dp = next_dp;58        }59 60        int result = MAX_COST;61        for (int p = 1; p <= n; p++) {62            result = Math.min(result, dp[target][p]);63        }64 65        return result >= MAX_COST ? -1 : result;66    }67}

Complexity

Time

O(m * target * n) We have an outer loop for `m` houses. Inside it, a loop for `target` neighborhoods. Inside that, we do two passes over `n` colors: one to find the two minimums and another to calculate the DP values. This gives `m * target * (O(n) + O(n)) = O(m * target * n)`.

Space

O(target * n) We only need to store the DP table for the previous house to compute the table for the current house. Thus, we use two tables of size `(target+1) x (n+1)`, resulting in this space complexity.

Trade-offs

Pros

Most efficient time complexity of O(m * target * n).
Optimal space complexity of O(target * n) due to space optimization.
Avoids recursion overhead and potential stack depth issues.

Cons

The logic, especially the state transitions and optimizations, can be more complex to reason about and implement correctly compared to the top-down approach.

Solutions

Solution

1class Solution {2public3  int minCost(int[] houses, int[][] cost, int m, int n, int target) {4    int[][][] f = new int[m][n + 1][target + 1];5    final int inf = 1 << 30;6    for (int[][] g : f) {7      for (int[] e : g) {8        Arrays.fill(e, inf);9      }10    }11    if (houses[0] == 0) {12      for (int j = 1; j <= n; ++j) {13        f[0][j][1] = cost[0][j - 1];14      }15    } else {16      f[0][houses[0]][1] = 0;17    }18    for (int i = 1; i < m; ++i) {19      if (houses[i] == 0) {20        for (int j = 1; j <= n; ++j) {21          for (int k = 1; k <= Math.min(target, i + 1); ++k) {22            for (int j0 = 1; j0 <= n; ++j0) {23              if (j == j0) {24                f[i][j][k] =25                    Math.min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]);26              } else {27                f[i][j][k] =28                    Math.min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]);29              }30            }31          }32        }33      } else {34        int j = houses[i];35        for (int k = 1; k <= Math.min(target, i + 1); ++k) {36          for (int j0 = 1; j0 <= n; ++j0) {37            if (j == j0) {38              f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k]);39            } else {40              f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1]);41            }42          }43        }44      }45    }46    int ans = inf;47    for (int j = 1; j <= n; ++j) {48      ans = Math.min(ans, f[m - 1][j][target]);49    }50    return ans >= inf ? -1 : ans;51  }52}

1class Solution {2public:3  int minCost(vector<int> &houses, vector<vector<int>> &cost, int m, int n,4              int target) {5    int f[m][n + 1][target + 1];6    memset(f, 0x3f, sizeof(f));7    if (houses[0] == 0) {8      for (int j = 1; j <= n; ++j) {9        f[0][j][1] = cost[0][j - 1];10      }11    } else {12      f[0][houses[0]][1] = 0;13    }14    for (int i = 1; i < m; ++i) {15      if (houses[i] == 0) {16        for (int j = 1; j <= n; ++j) {17          for (int k = 1; k <= min(target, i + 1); ++k) {18            for (int j0 = 1; j0 <= n; ++j0) {19              if (j == j0) {20                f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]);21              } else {22                f[i][j][k] =23                    min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]);24              }25            }26          }27        }28      } else {29        int j = houses[i];30        for (int k = 1; k <= min(target, i + 1); ++k) {31          for (int j0 = 1; j0 <= n; ++j0) {32            if (j == j0) {33              f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]);34            } else {35              f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1]);36            }37          }38        }39      }40    }41    int ans = 0x3f3f3f3f;42    for (int j = 1; j <= n; ++j) {43      ans = min(ans, f[m - 1][j][target]);44    }45    return ans == 0x3f3f3f3f ? -1 : ans;46  }47};

1class Solution:2    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int: f = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)] if houses[0] == 0: for j, c in enumerate(cost[0], 1): f[0][j][1] = c else: f[0][houses[0]][1] = 0 for i in range(1, m): if houses[i] == 0: for j in range(1, n + 1): for k in range(1, min(target + 1, i + 2)): for j0 in range(1, n + 1): if j == j0: f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]) else: f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]) else: j = houses[i] for k in range(1, min(target + 1, i + 2)): for j0 in range(1, n + 1): if j == j0: f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]) else: f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1]) ans = min(f[- 1][j][target] for j in range(1, n + 1)) return - 1 if ans >= inf else ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem