LeetCode 3429 - Paint House IV

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem is asking us to paint n houses arranged in a line with three available colors for each house, minimizing the total painting cost while satisfying two constraints. The first constraint is the standard one from the classic "Paint House" problem: no two adjacent houses can have the same color. The second constraint is new and requires that houses symmetric with respect to the row ends-meaning equidistant from the first and last house-cannot be painted the same color. For example, if n = 6, house pairs (0, 5), (1, 4), and (2, 3) must have different colors.

The input is an integer n and a 2D array cost of size n x 3, where cost[i][j] represents the cost to paint house i with color j + 1. The output is a single integer representing the minimum total cost to paint all houses satisfying the constraints.

Key constraints to note are that n is even and can be as large as 10^5, and each painting cost can also be up to 10^5. This immediately rules out any solution that tries all permutations of colors, as the total number of combinations grows exponentially.

Important edge cases include the smallest valid n = 2, when all costs are the same, or when the cheapest options for adjacent or symmetric houses conflict, requiring careful selection of alternatives.

Approaches

A brute-force approach would enumerate all possible sequences of colors for the houses, check each sequence for adjacency and symmetry constraints, and compute the total cost for valid sequences. While correct, this method is infeasible because there are 3^n possible sequences, which becomes astronomical even for moderate n.

The key observation for an optimal approach is that we can split the problem in half. Because n is even and the symmetry constraint pairs houses from the start and end, we only need to consider n/2 pairs. For each pair (i, n-1-i), the two houses must have different colors, and we can compute the minimum cost for painting each possible color combination. Once we do this for all pairs, the problem reduces to a dynamic programming problem similar to "Paint House," where the DP state only needs to track the previous pair's coloring to enforce the adjacency constraint.

We define a DP table where dp[i][c1][c2] is the minimum cost to paint the first i+1 pairs such that the i-th pair is painted with colors (c1, c2) from left to right. Transitioning to the next pair requires checking that c1 is not equal to the previous left house color and c2 is not equal to the previous right house color. By iterating through all valid color combinations, we can efficiently compute the minimum total cost.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n)	O(n)	Tries all possible color sequences; impractical for n up to 10^5
Optimal	O(n)	O(1)	Uses DP on pairs with 3x3 color combinations; constant space per pair

Algorithm Walkthrough

Pair the houses as (i, n-1-i) for i = 0 to n/2 - 1.
For each pair, enumerate all 3x3 possible color combinations (c1, c2) where c1 != c2 to satisfy the symmetry constraint.
Initialize a DP array for the first pair with the cost of painting both houses using each valid color combination.
For each subsequent pair, compute the minimum cost to paint the pair given the previous pair’s color choices while ensuring no two adjacent houses have the same color. For this, only consider transitions where the left color of the current pair is not equal to the left color of the previous pair, and the right color is not equal to the right color of the previous pair.
After processing all pairs, the minimum value in the DP array for the last pair is the answer.

Why it works: By processing houses in symmetric pairs and only storing valid color combinations for each pair, we maintain both the adjacency and symmetry constraints. Each DP state considers the optimal solution for the prefix of pairs ending at that position, ensuring global optimality.

Python Solution

from typing import List

class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        pairs = n // 2
        dp = [[0]*3 for _ in range(3)]
        
        # Initialize DP for the first pair
        for c1 in range(3):
            for c2 in range(3):
                if c1 != c2:
                    dp[c1][c2] = cost[0][c1] + cost[n-1][c2]
                else:
                    dp[c1][c2] = float('inf')
        
        for i in range(1, pairs):
            new_dp = [[float('inf')]*3 for _ in range(3)]
            for c1 in range(3):
                for c2 in range(3):
                    if c1 == c2:
                        continue
                    for pc1 in range(3):
                        for pc2 in range(3):
                            if pc1 != c1 and pc2 != c2:
                                new_dp[c1][c2] = min(new_dp[c1][c2], dp[pc1][pc2] + cost[i][c1] + cost[n-1-i][c2])
            dp = new_dp
        
        return min(min(row) for row in dp)

The Python implementation first initializes the DP for the first pair using all valid color combinations that satisfy the symmetry constraint. For each subsequent pair, it updates the DP table by considering transitions from all previous valid color combinations while enforcing the adjacency constraint. Finally, the minimum value across all color combinations for the last pair is returned.

Go Solution

func minCost(n int, cost [][]int) int64 {
    pairs := n / 2
    dp := [3][3]int64{}
    
    // Initialize DP for the first pair
    for c1 := 0; c1 < 3; c1++ {
        for c2 := 0; c2 < 3; c2++ {
            if c1 != c2 {
                dp[c1][c2] = int64(cost[0][c1] + cost[n-1][c2])
            } else {
                dp[c1][c2] = 1 << 60
            }
        }
    }
    
    for i := 1; i < pairs; i++ {
        var newDp [3][3]int64
        for c1 := 0; c1 < 3; c1++ {
            for c2 := 0; c2 < 3; c2++ {
                newDp[c1][c2] = 1 << 60
                if c1 == c2 {
                    continue
                }
                for pc1 := 0; pc1 < 3; pc1++ {
                    for pc2 := 0; pc2 < 3; pc2++ {
                        if pc1 != c1 && pc2 != c2 {
                            val := dp[pc1][pc2] + int64(cost[i][c1] + cost[n-1-i][c2])
                            if val < newDp[c1][c2] {
                                newDp[c1][c2] = val
                            }
                        }
                    }
                }
            }
        }
        dp = newDp
    }
    
    res := int64(1 << 60)
    for c1 := 0; c1 < 3; c1++ {
        for c2 := 0; c2 < 3; c2++ {
            if dp[c1][c2] < res {
                res = dp[c1][c2]
            }
        }
    }
    return res
}

The Go solution mirrors the Python logic but uses fixed-size arrays for DP to avoid dynamic allocation. Integer overflow is mitigated by using int64 for all calculations.

Worked Examples

Example 1: n = 4

Pairs: (0,3) and (1,2)

First pair costs:

(0,1): 3+3=6
(0,2): 3+5=8
(1,0): 5+7=12
(1,2): 5+5=10
(2,0): 7+7=14
(2,1): 7+3=10

Second pair transitions from first pair while respecting adjacency:

Minimum total cost = 9

Example 2: n = 6

Pairs: (0,5), (1,4), (2,3)

Compute DP iteratively for each pair respecting adjacency and symmetry. Minimum total cost = 18.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each of the n/2 pairs has 3x3 = 9 possible color combinations, and each transition checks 9 previous states, resulting in 9x9 operations per pair. Constant factor is small.
Space	O(1)	Only two 3x3 DP arrays are maintained, independent of n.

The linear time complexity is acceptable for n up to 10^5.