# Paint House IV **Difficulty:** MEDIUM [External](https://leetcode.com/problems/paint-house-iv) Canonical: https://scaleengineer.com/dsa/problems/paint-house-iv **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Data structures:** Array --- ## Problem You are given an **even** integer `n` representing the number of houses arranged in a straight line, and a 2D array `cost` of size `n x 3`, where `cost[i][j]` represents the cost of painting house `i` with color `j + 1`. The houses will look **beautiful** if they satisfy the following conditions: * No **two** adjacent houses are painted the same color. * Houses **equidistant** from the ends of the row are **not** painted the same color. For example, if `n = 6`, houses at positions `(0, 5)`, `(1, 4)`, and `(2, 3)` are considered equidistant. Return the **minimum** cost to paint the houses such that they look **beautiful**. **Example 1:** **Input:** n = 4, cost = \[\[3,5,7\],\[6,2,9\],\[4,8,1\],\[7,3,5\]\] **Output:** 9 **Explanation:** The optimal painting sequence is `[1, 2, 3, 2]` with corresponding costs `[3, 2, 1, 3]`. This satisfies the following conditions: * No adjacent houses have the same color. * Houses at positions 0 and 3 (equidistant from the ends) are not painted the same color `(1 != 2)`. * Houses at positions 1 and 2 (equidistant from the ends) are not painted the same color `(2 != 3)`. The minimum cost to paint the houses so that they look beautiful is `3 + 2 + 1 + 3 = 9`. **Example 2:** **Input:** n = 6, cost = \[\[2,4,6\],\[5,3,8\],\[7,1,9\],\[4,6,2\],\[3,5,7\],\[8,2,4\]\] **Output:** 18 **Explanation:** The optimal painting sequence is `[1, 3, 2, 3, 1, 2]` with corresponding costs `[2, 8, 1, 2, 3, 2]`. This satisfies the following conditions: * No adjacent houses have the same color. * Houses at positions 0 and 5 (equidistant from the ends) are not painted the same color `(1 != 2)`. * Houses at positions 1 and 4 (equidistant from the ends) are not painted the same color `(3 != 1)`. * Houses at positions 2 and 3 (equidistant from the ends) are not painted the same color `(2 != 3)`. The minimum cost to paint the houses so that they look beautiful is `2 + 8 + 1 + 2 + 3 + 2 = 18`. **Constraints:** * `2 <= n <= 105` * `n` is even. * `cost.length == n` * `cost[i].length == 3` * `0 <= cost[i][j] <= 105` # Approaches ## Top-Down Dynamic Programming (Memoization) This approach uses recursion to explore the choices for painting each pair of houses, starting from the outermost pair `(0, n-1)`. The problem has optimal substructure and overlapping subproblems, making it suitable for dynamic programming. To avoid recomputing results for the same subproblems, we use a memoization table. A subproblem is defined by the index of the house pair we are currently considering and the colors of the previous pair. **Time:** O(n). The number of states is `(n/2) * 3 * 3 = O(n)`. Each state is computed once, and the computation involves a constant number of operations (loops of size 3), so the total time complexity is `O(n)`. · **Space:** O(n). The space is dominated by the memoization table of size `(n/2) * 3 * 3`, which is `O(n)`. The recursion stack depth also contributes `O(n)` space. **Pros:** Conceptually straightforward, as it directly translates the recursive structure of the problem.; Memoization avoids recomputing subproblems, making it efficient. **Cons:** Can lead to stack overflow for very large `n` if the recursion depth limit is low, although `n/2` up to 50,000 is generally acceptable.; Slightly higher constant factor overhead due to function calls compared to an iterative approach. ### Explanation We can model this problem by considering pairs of houses that are equidistant from the ends: `(i, n-1-i)`. The coloring decision for pair `i` depends on the decision for pair `i-1` due to the adjacency constraint. This dependency structure lends itself to a recursive solution. We define a recursive function `solve(i, prev_c1, prev_c2)` that computes the minimum cost to paint pairs from `i` to `n/2 - 1`, given that the previous pair `i-1` was colored with `(prev_c1, prev_c2)`. The state for our memoization table `memo` will be `[i][prev_c1][prev_c2]`. The base case for the recursion is when `i` reaches `n/2`, meaning all pairs have been painted, and the cost from this point onwards is 0. In the recursive step for pair `i`, we try every possible color combination `(c1, c2)` for houses `i` and `n-1-i`. We check if the combination is valid against the colors of the previous pair `(prev_c1, prev_c2)` and the problem's constraints (`c1 != c2`). For each valid combination, we calculate the cost for the current pair and add the result of the recursive call for the next pair, `solve(i+1, c1, c2)`. We take the minimum over all these possibilities. The initial calls are made from a wrapper function that iterates through all valid colorings for the first pair `(0, n-1)` and calls `solve(1, ...)` for each, finding the overall minimum. ```java class Solution { private int n; private int[][] cost; private long[][][] memo; public int minCost(int n, int[][] cost) { this.n = n; this.cost = cost; // memo[i][prev_c1][prev_c2] this.memo = new long[n / 2][3][3]; for (int i = 0; i < n / 2; i++) { for (int j = 0; j < 3; j++) { Arrays.fill(this.memo[i][j], -1); } } long totalMinCost = Long.MAX_VALUE; // Loop for the first pair (i=0) for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { if (c1 == c2) continue; long currentCost = cost[0][c1] + cost[n - 1][c2]; long futureCost = solve(1, c1, c2); if (futureCost != Long.MAX_VALUE) { totalMinCost = Math.min(totalMinCost, currentCost + futureCost); } } } return (int) totalMinCost; } // solve for pairs from i onwards, given previous colors were prev_c1, prev_c2 private long solve(int i, int prev_c1, int prev_c2) { if (i == n / 2) { return 0; } if (memo[i][prev_c1][prev_c2] != -1) { return memo[i][prev_c1][prev_c2]; } long minCost = Long.MAX_VALUE; // Loop for current pair (i) for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { if (c1 == c2 || c1 == prev_c1 || c2 == prev_c2) continue; long currentPairCost = cost[i][c1] + cost[n - 1 - i][c2]; long futureCost = solve(i + 1, c1, c2); if (futureCost != Long.MAX_VALUE) { minCost = Math.min(minCost, currentPairCost + futureCost); } } } return memo[i][prev_c1][prev_c2] = minCost; } } ``` ### Algorithm * Define a recursive function, say `solve(i, prev_c1, prev_c2)`, which calculates the minimum cost to paint house pairs from `i` to `n/2 - 1`, given that house `i-1` was painted with `prev_c1` and house `n-i` was painted with `prev_c2`. * Use a 3D array `memo[n/2][3][3]` to store the results of subproblems to avoid re-computation. * **Base Case:** When `i == n/2`, all houses are painted, so the cost is 0. * **Recursive Step:** For the current pair `i`, iterate through all possible color combinations `(c1, c2)` for houses `i` and `n-1-i`. A combination is valid if: 1. `c1 != c2` (symmetric condition). 2. `c1 != prev_c1` (adjacency with house `i-1`). 3. `c2 != prev_c2` (adjacency with house `n-i`). * For each valid pair `(c1, c2)`, the cost is `(cost[i][c1] + cost[n-1-i][c2]) + solve(i+1, c1, c2)`. The function finds the minimum cost among all valid choices. * The main function initiates the process by considering all valid colorings for the first pair `i=0` and calling the recursive function for `i=1`. ## Bottom-Up Dynamic Programming This approach is an iterative, or bottom-up, version of the recursive solution. We build the solution from the first pair of houses to the last. By systematically filling a DP table, we can solve the problem without recursion. This approach often has slightly better performance in practice due to the absence of recursive function call overhead. **Time:** O(n). We iterate through `n/2` pairs. For each pair, we have a constant number of states (`3*3`) and each state transition takes constant time (`3*3` lookups). The total time is `(n/2) * 9 * 9`, which is `O(n)`. · **Space:** O(n). The DP table `dp` has dimensions `(n/2) x 3 x 3`, resulting in `O(n)` space complexity. **Pros:** Avoids recursion overhead and potential stack overflow issues.; The iterative logic can be easier to reason about for some developers. **Cons:** Uses `O(n)` space, which is suboptimal for this problem's constraints and can be a concern for very large `n`. ### Explanation We use a 3D DP table, `dp[i][c1][c2]`, to store the minimum cost. The state `dp[i][c1][c2]` represents the minimum cost to paint the first `i+1` pairs of houses (from pair 0 to `i`), where the `i`-th pair of houses (`i`, `n-1-i`) are painted with colors `c1` and `c2` respectively. The process starts by initializing the DP table for the base case, which is the first pair of houses `i=0`. For each valid color combination `(c1, c2)` where `c1 != c2`, `dp[0][c1][c2]` is set to `cost[0][c1] + cost[n-1][c2]`. Then, we iterate from the second pair (`i=1`) up to the last pair (`i=n/2 - 1`). For each pair `i` and each possible color combination `(c1, c2)`, we calculate `dp[i][c1][c2]`. This value is the sum of the cost to paint the current pair `i` with `(c1, c2)` and the minimum cost to paint all previous pairs `0` to `i-1` ending with a valid color combination `(pc1, pc2)`. A previous combination is valid if `pc1 != c1` and `pc2 != c2`. After the loops complete, the DP table for the last pair, `dp[n/2 - 1]`, contains the minimum costs for all possible valid final colorings. The overall minimum cost is the minimum value found in this last slice of the DP table. ```java class Solution { public int minCost(int n, int[][] cost) { long[][][] dp = new long[n / 2][3][3]; // Base case: i = 0 for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { if (c1 != c2) { dp[0][c1][c2] = cost[0][c1] + cost[n - 1][c2]; } else { dp[0][c1][c2] = Long.MAX_VALUE; } } } // Iteration for i = 1 to n/2 - 1 for (int i = 1; i < n / 2; i++) { for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { if (c1 == c2) { dp[i][c1][c2] = Long.MAX_VALUE; continue; } long minPrevCost = Long.MAX_VALUE; for (int pc1 = 0; pc1 < 3; pc1++) { for (int pc2 = 0; pc2 < 3; pc2++) { if (pc1 != c1 && pc2 != c2) { minPrevCost = Math.min(minPrevCost, dp[i - 1][pc1][pc2]); } } } long currentPairCost = cost[i][c1] + cost[n - 1 - i][c2]; if (minPrevCost != Long.MAX_VALUE) { dp[i][c1][c2] = currentPairCost + minPrevCost; } else { dp[i][c1][c2] = Long.MAX_VALUE; } } } } long minTotalCost = Long.MAX_VALUE; for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { minTotalCost = Math.min(minTotalCost, dp[n / 2 - 1][c1][c2]); } } return (int) minTotalCost; } } ``` ### Algorithm * Define a 3D DP table, `dp[i][c1][c2]`, to store the minimum cost to paint the first `i` pairs of houses, with house `i-1` painted `c1` and house `n-i` painted `c2`. * The table size will be `(n/2) x 3 x 3`. * **Base Case (i=0):** Initialize the first slice `dp[0]` for the first pair of houses `(0, n-1)`. `dp[0][c1][c2] = cost[0][c1] + cost[n-1][c2]` for all `c1 != c2`. * **Transition:** Iterate from `i = 1` to `n/2 - 1`. For each pair `i`, calculate `dp[i][c1][c2]` for all valid color pairs `(c1, c2)`. * `dp[i][c1][c2] = (cost[i][c1] + cost[n-1-i][c2]) + min(dp[i-1][pc1][pc2])`, where the minimum is over all previous color pairs `(pc1, pc2)` such that `pc1 != c1` and `pc2 != c2`. * **Final Result:** After filling the table, the minimum value in the last slice, `dp[n/2 - 1]`, is the answer. ## Space-Optimized Bottom-Up DP This is the most efficient approach, improving upon the bottom-up DP by optimizing space. Since the DP state for pair `i` only depends on the state of pair `i-1`, we don't need to store the entire history. We only need to keep track of the DP values for the previous step, reducing the space complexity from `O(n)` to `O(1)`. The time complexity remains `O(n)` but can be improved by a constant factor with a smarter transition. **Time:** O(n). The main loop runs `n/2` times, and the work inside is constant. The overall complexity is linear in `n`. · **Space:** O(1). We only use a few `3x3` arrays to store the DP states, which is constant space regardless of `n`. **Pros:** Most efficient solution in terms of space.; Optimal for problems with large constraints on `n`. **Cons:** The logic, especially with transition optimizations, can be more complex to implement correctly. ### Explanation The key observation for this optimization is that `dp[i]` only depends on `dp[i-1]`. This allows us to discard the DP states for `i-2` and earlier. We can achieve this by using only two `3x3` arrays: one to hold the DP values for the previous pair (`dp`) and another to compute the values for the current pair (`next_dp`). The process is as follows: 1. Initialize a `3x3` array `dp` with the costs for the first pair `(0, n-1)`. 2. Iterate from `i = 1` to `n/2 - 1`. 3. Inside the loop, create a new `3x3` array `next_dp`. 4. Calculate the entries of `next_dp` using the values from `dp`. The transition logic remains the same: `next_dp[c1][c2]` is the cost of painting pair `i` with `(c1, c2)` plus the minimum valid cost from the `dp` table. 5. After `next_dp` is computed, replace `dp` with `next_dp` for the next iteration. To make the transition faster, instead of a nested `3x3` loop to find the minimum previous cost, we can pre-calculate the two smallest values for each row of the `dp` table. This allows finding the required minimum in constant time, reducing the work inside the main loop. ```java class Solution { public int minCost(int n, int[][] cost) { long[][] dp = new long[3][3]; // Base case: i = 0 for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { if (c1 != c2) { dp[c1][c2] = cost[0][c1] + cost[n - 1][c2]; } else { dp[c1][c2] = Long.MAX_VALUE; } } } // Iteration for i = 1 to n/2 - 1 for (int i = 1; i < n / 2; i++) { long[][] next_dp = new long[3][3]; // Pre-calculate min and second min for each row of dp long[] rowMins = new long[3]; long[] rowSecondMins = new long[3]; int[] rowMinIndices = new int[3]; for(int r = 0; r < 3; r++) { long m1 = Long.MAX_VALUE, m2 = Long.MAX_VALUE; int idx1 = -1; for (int c = 0; c < 3; c++) { if (dp[r][c] < m1) { m2 = m1; m1 = dp[r][c]; idx1 = c; } else if (dp[r][c] < m2) { m2 = dp[r][c]; } } rowMins[r] = m1; rowSecondMins[r] = m2; rowMinIndices[r] = idx1; } for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { if (c1 == c2) { next_dp[c1][c2] = Long.MAX_VALUE; continue; } long minPrevCost = Long.MAX_VALUE; for (int pc1 = 0; pc1 < 3; pc1++) { if (pc1 == c1) continue; if (rowMinIndices[pc1] != c2) { minPrevCost = Math.min(minPrevCost, rowMins[pc1]); } else { minPrevCost = Math.min(minPrevCost, rowSecondMins[pc1]); } } long currentPairCost = cost[i][c1] + cost[n - 1 - i][c2]; if (minPrevCost != Long.MAX_VALUE) { next_dp[c1][c2] = currentPairCost + minPrevCost; } else { next_dp[c1][c2] = Long.MAX_VALUE; } } } dp = next_dp; } long minTotalCost = Long.MAX_VALUE; for (int c1 = 0; c1 < 3; c1++) { for (int c2 = 0; c2 < 3; c2++) { minTotalCost = Math.min(minTotalCost, dp[c1][c2]); } } return (int) minTotalCost; } } ``` ### Algorithm * Observe that the calculation for pair `i` only depends on the results from pair `i-1`. * Instead of a full `O(n)` DP table, use two `3x3` arrays: `dp` for the previous state (`i-1`) and `next_dp` for the current state (`i`). * **Initialization:** Initialize `dp` for the first pair `i=0` as in the previous approaches. * **Iteration:** Loop from `i = 1` to `n/2 - 1`. 1. In each iteration, compute `next_dp` based on the values in `dp`. 2. To optimize the transition, for each row `pc1` of `dp`, pre-calculate its minimum and second minimum values. 3. When computing `next_dp[c1][c2]`, the minimum previous cost from row `pc1` (where `pc1 != c1`) can be found in `O(1)` using the pre-calculated values. 4. After `next_dp` is fully computed, update `dp = next_dp`. * **Final Result:** After the loop, the minimum value in the final `dp` array is the answer.