LeetCode Problem 1473

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

LeetCode 1473 - Paint House III

Problem Understanding

This problem asks us to paint a row of houses while satisfying two constraints simultaneously:

1. Every house must end up painted with one of the available colors.
2. The final arrangement must contain exactly target neighborhoods.

A neighborhood is defined as a maximal contiguous group of houses painted the same color. For example, the sequence:

[1,1,2,2,3,1,1]

contains four neighborhoods:

[1,1], [2,2], [3], [1,1]

The input provides three important pieces of information:

• houses[i]

• If non-zero, the house is already painted and cannot be changed.

• If zero, the house is unpainted and we may choose any color for it.

• cost[i][j]

• The cost of painting house i with color j + 1.

• target

• The exact number of neighborhoods required in the final configuration.

The goal is to minimize the total painting cost while ensuring the final arrangement has exactly target neighborhoods.

The constraints are important:

• m <= 100
• n <= 20
• target <= 100

These limits immediately suggest that brute force enumeration of all color assignments is impossible. Even for moderate values like:

20^100

the number of possibilities becomes astronomically large.

The problem also contains several tricky edge cases:

• Some houses are already painted and cannot be modified.
• The existing painted houses may already exceed the target neighborhood count.
• A new neighborhood is formed whenever the current house color differs from the previous house color.
• Multiple painting choices may lead to the same number of neighborhoods but different costs.
• It may be impossible to achieve exactly target neighborhoods.

Because we need both optimal cost minimization and precise structural tracking of neighborhoods, this strongly points toward dynamic programming.

Approaches

Brute Force Approach

The brute force solution tries every possible coloring assignment for the unpainted houses.

For each unpainted house, we recursively choose one of the n colors. After assigning colors to all houses, we count the number of neighborhoods and compute the total cost. If the neighborhood count equals target, we update the minimum answer.

This approach is correct because it explores every valid painting configuration. Eventually, the minimum-cost valid arrangement will be found.

However, it is far too slow.

Suppose there are k unpainted houses. Then the total number of assignments is:

n^k

In the worst case:

20^100

which is completely infeasible.

Key Insight for the Optimal Solution

The crucial observation is that when processing houses from left to right, the future only depends on:

• The current position
• The previous house color
• The number of neighborhoods formed so far

This means we can define a dynamic programming state.

Let:

dp[i][c][t]

represent the minimum cost to paint houses up to index i such that:

• House i has color c
• We have formed exactly t neighborhoods

The neighborhood count changes only when the current color differs from the previous color.

This converts an exponential search into a polynomial-time dynamic programming solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^m)	O(m)	Tries every coloring assignment
Optimal Dynamic Programming	O(m × n² × target)	O(m × n × target)	Tracks position, color, and neighborhoods

Algorithm Walkthrough

Step 1: Define the DP State

We define:

dp[i][color][groups]

as the minimum cost to process houses from 0 to i where:

• House i ends with color
• Exactly groups neighborhoods exist

If a state is impossible, we store infinity.

This state captures all information needed for future transitions.

Step 2: Initialize the First House

For house 0:

• If already painted, only one color is allowed.
• Otherwise, we try every possible color.

Every valid coloring of the first house creates exactly one neighborhood.

Step 3: Process Houses Left to Right

For every house i, we examine every possible current color.

There are two cases:

Same Color as Previous House

If:

current_color == previous_color

then the neighborhood count does not increase.

Transition:

dp[i][current][groups]
=
min(
    dp[i][current][groups],
    dp[i-1][previous][groups] + paint_cost
)

Different Color from Previous House

If:

current_color != previous_color

then a new neighborhood begins.

Transition:

dp[i][current][groups]
=
min(
    dp[i][current][groups],
    dp[i-1][previous][groups-1] + paint_cost
)

Step 4: Respect Pre-Painted Houses

If a house is already painted:

• We cannot choose another color.
• The painting cost becomes zero because no painting occurs.

This restriction is enforced during transitions.

Step 5: Extract the Final Answer

After processing all houses, we examine:

dp[m-1][color][target]

for all colors.

The smallest value is the answer.

If every value is infinity, then no valid arrangement exists, so we return -1.

Why it works

The algorithm works because every DP state represents the optimal way to reach a specific configuration:

• Up to a certain house
• Ending with a certain color
• Having a certain number of neighborhoods

Every valid painting arrangement corresponds to exactly one sequence of DP transitions. Since each state stores the minimum achievable cost, the final answer must be optimal.

The neighborhood count is handled correctly because the transition explicitly checks whether the current color matches the previous color.

Python Solution

from typing import List

class Solution:
    def minCost(
        self,
        houses: List[int],
        cost: List[List[int]],
        m: int,
        n: int,
        target: int
    ) -> int:
        
        INF = float('inf')
        
        # dp[i][color][groups]
        dp = [[[INF] * (target + 1) for _ in range(n)] for _ in range(m)]
        
        # Initialize first house
        if houses[0] != 0:
            color = houses[0] - 1
            dp[0][color][1] = 0
        else:
            for color in range(n):
                dp[0][color][1] = cost[0][color]
        
        # Process remaining houses
        for i in range(1, m):
            
            for curr_color in range(n):
                
                # Skip invalid colors for pre-painted houses
                if houses[i] != 0 and houses[i] - 1 != curr_color:
                    continue
                
                paint_cost = 0 if houses[i] != 0 else cost[i][curr_color]
                
                for prev_color in range(n):
                    for groups in range(1, target + 1):
                        
                        if dp[i - 1][prev_color][groups] == INF:
                            continue
                        
                        # Same neighborhood
                        if curr_color == prev_color:
                            dp[i][curr_color][groups] = min(
                                dp[i][curr_color][groups],
                                dp[i - 1][prev_color][groups] + paint_cost
                            )
                        
                        # New neighborhood
                        elif groups < target:
                            dp[i][curr_color][groups + 1] = min(
                                dp[i][curr_color][groups + 1],
                                dp[i - 1][prev_color][groups] + paint_cost
                            )
        
        answer = min(dp[m - 1][color][target] for color in range(n))
        
        return -1 if answer == INF else answer

The implementation begins by creating a three-dimensional DP table initialized to infinity. Infinity represents states that are currently impossible to reach.

The first house is handled separately because it always creates the first neighborhood. If the house is already painted, only one color is valid. Otherwise, every color choice is initialized with its corresponding painting cost.

The main loop processes houses from left to right. For each house, the algorithm iterates through every possible current color and every possible previous color.

If the current house is pre-painted, invalid color choices are skipped immediately. This prevents illegal transitions.

For each valid transition:

• If the color stays the same, the neighborhood count remains unchanged.
• If the color changes, the neighborhood count increases by one.

The DP table stores the minimum cost among all possible ways to reach each state.

Finally, the algorithm scans all colors for the last house with exactly target neighborhoods and returns the minimum value.

Go Solution

package main

import "math"

func minCost(houses []int, cost [][]int, m int, n int, target int) int {
	INF := math.MaxInt32

	// dp[i][color][groups]
	dp := make([][][]int, m)

	for i := 0; i < m; i++ {
		dp[i] = make([][]int, n)

		for j := 0; j < n; j++ {
			dp[i][j] = make([]int, target+1)

			for k := 0; k <= target; k++ {
				dp[i][j][k] = INF
			}
		}
	}

	// Initialize first house
	if houses[0] != 0 {
		color := houses[0] - 1
		dp[0][color][1] = 0
	} else {
		for color := 0; color < n; color++ {
			dp[0][color][1] = cost[0][color]
		}
	}

	// Process remaining houses
	for i := 1; i < m; i++ {

		for currColor := 0; currColor < n; currColor++ {

			// Skip invalid colors for pre-painted houses
			if houses[i] != 0 && houses[i]-1 != currColor {
				continue
			}

			paintCost := 0
			if houses[i] == 0 {
				paintCost = cost[i][currColor]
			}

			for prevColor := 0; prevColor < n; prevColor++ {

				for groups := 1; groups <= target; groups++ {

					if dp[i-1][prevColor][groups] == INF {
						continue
					}

					// Same neighborhood
					if currColor == prevColor {

						if dp[i][currColor][groups] >
							dp[i-1][prevColor][groups]+paintCost {

							dp[i][currColor][groups] =
								dp[i-1][prevColor][groups] + paintCost
						}

					} else if groups < target {

						// New neighborhood
						if dp[i][currColor][groups+1] >
							dp[i-1][prevColor][groups]+paintCost {

							dp[i][currColor][groups+1] =
								dp[i-1][prevColor][groups] + paintCost
						}
					}
				}
			}
		}
	}

	answer := INF

	for color := 0; color < n; color++ {
		if answer > dp[m-1][color][target] {
			answer = dp[m-1][color][target]
		}
	}

	if answer == INF {
		return -1
	}

	return answer
}

The Go implementation follows the same DP structure as the Python solution, but uses explicit slice allocation for the three-dimensional DP array.

Go does not provide a built-in infinity value for integers, so math.MaxInt32 is used as a large sentinel value.

Unlike Python's min() function, Go requires explicit comparisons before updating DP states.

The logic and state transitions remain identical between the two implementations.

Worked Examples

Example 1

Input

houses = [0,0,0,0,0]
target = 3

Initialization

First house possibilities:

Color	Cost	Neighborhoods
1	1	1
2	10	1

After House 1

Possible states:

Previous	Current	Groups	Total Cost
1	1	1	11
1	2	2	2
2	1	2	20
2	2	1	11

The cheapest state with 2 groups is:

[1,2]
cost = 2

Continuing the DP

Eventually the optimal configuration becomes:

[1,2,2,1,1]

Neighborhoods:

[1], [2,2], [1,1]

Total cost:

1 + 1 + 1 + 1 + 5 = 9

Final answer:

9

Example 2

Input

houses = [0,2,1,2,0]
target = 3

Key Observation

Middle houses are already painted:

[?,2,1,2,?]

Current neighborhoods:

[2], [1], [2]

already equals 3 if the first and last houses are painted color 2.

Optimal Choice

Paint:

[2,2,1,2,2]

Cost:

House	Color	Cost
0	2	10
4	2	1

Total:

11

Example 3

Input

houses = [3,1,2,3]
target = 3

Existing Neighborhoods

The houses already form:

[3], [1], [2], [3]

which equals 4 neighborhoods.

Since houses are already painted, nothing can be changed.

Therefore reaching exactly 3 neighborhoods is impossible.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n² × target)	For each house, we try all current and previous colors
Space	O(m × n × target)	DP table stores all states

The time complexity comes from four nested dimensions:

• m houses
• n current colors
• n previous colors
• target neighborhood counts

Given:

m <= 100
n <= 20
target <= 100

this complexity is acceptable.

The space complexity comes from storing the DP table for every house, color, and neighborhood count.

Test Cases

sol = Solution()

# Example 1
assert sol.minCost(
    [0,0,0,0,0],
    [[1,10],[10,1],[10,1],[1,10],[5,1]],
    5,
    2,
    3
) == 9  # Basic example with all houses unpainted

# Example 2
assert sol.minCost(
    [0,2,1,2,0],
    [[1,10],[10,1],[10,1],[1,10],[5,1]],
    5,
    2,
    3
) == 11  # Mixed painted and unpainted houses

# Example 3
assert sol.minCost(
    [3,1,2,3],
    [[1,1,1],[1,1,1],[1,1,1],[1,1,1]],
    4,
    3,
    3
) == -1  # Impossible because neighborhoods already exceed target

# Single house
assert sol.minCost(
    [0],
    [[5,3,2]],
    1,
    3,
    1
) == 2  # Choose cheapest color

# Single already painted house
assert sol.minCost(
    [2],
    [[1,1,1]],
    1,
    3,
    1
) == 0  # No painting needed

# Impossible target
assert sol.minCost(
    [0,0],
    [[1,1],[1,1]],
    2,
    2,
    3
) == -1  # Cannot have more neighborhoods than houses

# All same color optimal
assert sol.minCost(
    [0,0,0],
    [[1,10],[1,10],[1,10]],
    3,
    2,
    1
) == 3  # One neighborhood is cheapest

# Force alternating colors
assert sol.minCost(
    [0,0,0],
    [[1,100],[100,1],[1,100]],
    3,
    2,
    3
) == 3  # Alternating pattern creates 3 neighborhoods

# Pre-painted constraints
assert sol.minCost(
    [1,0,1],
    [[1,1],[5,1],[1,1]],
    3,
    2,
    2
) == 1  # Middle house painted differently

# Large target equal to houses
assert sol.minCost(
    [0,0,0,0],
    [[1,1],[1,1],[1,1],[1,1]],
    4,
    2,
    4
) == 4  # Every house must differ from previous

Test Case Summary

Test	Why
All houses unpainted	Validates normal DP transitions
Mixed painted and unpainted	Ensures fixed colors are respected
Impossible configuration	Verifies correct -1 handling
Single house	Smallest valid input
Already painted single house	Ensures zero additional cost
Target greater than houses	Impossible structural constraint
One neighborhood optimal	Tests same-color transitions
Alternating colors	Tests neighborhood increments
Fixed painted endpoints	Ensures neighborhood counting correctness
Maximum neighborhood formation	Tests frequent color changes

Edge Cases

One important edge case occurs when houses are already painted in a way that exceeds the target neighborhood count. For example:

[1,2,3]
target = 2

The houses already contain three neighborhoods, and no repainting is allowed. A naive solution might still attempt transitions, but the correct answer is immediately impossible. The DP naturally handles this because no valid state reaches the target.

Another tricky case happens when all houses are unpainted and multiple colorings produce the same number of neighborhoods. The algorithm must choose the minimum-cost configuration rather than the first valid one encountered. The DP table solves this by storing the minimum cost for every state.

A third important edge case involves neighborhood boundaries. Whenever the current color differs from the previous color, the neighborhood count must increase exactly once. Incorrect implementations often double-count or fail to count transitions properly. The DP transition logic explicitly separates:

• Same color transitions
• Different color transitions

which guarantees accurate neighborhood tracking.

A final subtle case appears when target == m. In this scenario, every adjacent pair of houses must have different colors. The DP handles this correctly because every color change increments the neighborhood count, making the final target achievable only through alternating colors.