Scale Engineer

Paint House IV

Med
#3047Time: 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.
Patterns
Dynamic Programming
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

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 →

Next problem