Problem Description

You have n houses arranged in a row, and each house must be painted with one of three colors: red, blue, or green. The challenge is that no two adjacent houses can have the same color.

You're given a cost matrix costs with dimensions n x 3, where:

• costs[i][0] represents the cost to paint house i with red
• costs[i][1] represents the cost to paint house i with blue
• costs[i][2] represents the cost to paint house i with green

Your task is to find the minimum total cost to paint all houses while ensuring that no two neighboring houses share the same color.

For example, if you have 3 houses with costs:

• House 0: red=17, blue=2, green=17
• House 1: red=16, blue=16, green=5
• House 2: red=14, blue=3, green=19

You need to choose one color for each house such that the total cost is minimized and adjacent houses have different colors. In this case, one optimal solution would be to paint house 0 blue (cost 2), house 1 green (cost 5), and house 2 blue (cost 3), for a total minimum cost of 10.

The solution uses dynamic programming with space optimization. Variables a, b, and c track the minimum cost to paint houses up to the current position if the current house is painted red, blue, or green respectively. For each house, the algorithm calculates the new minimum costs by adding the current painting cost to the minimum of the previous costs (excluding the same color to avoid adjacent houses having the same color).

Intuition

The key insight is that for each house, we need to make a decision based on the choices we made for the previous house. Since adjacent houses can't have the same color, if we painted the previous house red, the current house can only be blue or green.

This naturally leads to a dynamic programming approach. For each house position, we need to track: what's the minimum cost if we paint this house red? What if we paint it blue? What if we paint it green?

Let's think about house i. If we want to paint it red, we need to look at the minimum cost of painting all houses up to i-1 where house i-1 was NOT painted red (so it was either blue or green). The minimum cost for painting house i red would be: min(cost_if_prev_blue, cost_if_prev_green) + cost_to_paint_current_red.

The same logic applies for the other two colors. This gives us the recurrence relation:

• dp[i][red] = min(dp[i-1][blue], dp[i-1][green]) + costs[i][red]
• dp[i][blue] = min(dp[i-1][red], dp[i-1][green]) + costs[i][blue]
• dp[i][green] = min(dp[i-1][red], dp[i-1][blue]) + costs[i][green]

The beautiful observation in the given solution is that we don't need a 2D array to store all these values. Since we only ever look at the previous house's costs, we can use just three variables (a, b, c) to track the minimum costs for the current position if painted red, blue, or green respectively. We update these three values as we iterate through each house, and at the end, the minimum among these three values gives us our answer.

This space optimization transforms an O(n) space solution into an O(1) space solution while maintaining O(n) time complexity.

Solution Approach

The solution implements a space-optimized dynamic programming approach using three variables to track the minimum costs.

Variable Initialization:

• a = 0: Minimum cost if the current house is painted red (color 0)
• b = 0: Minimum cost if the current house is painted blue (color 1)
• c = 0: Minimum cost if the current house is painted green (color 2)

These start at 0 because before painting any house, the cost is 0.

Main Loop: The algorithm iterates through each house's costs using tuple unpacking:

for ca, cb, cc in costs:

Where ca, cb, cc represent the costs of painting the current house with red, blue, and green respectively.

State Transition: For each house, we simultaneously update all three variables:

a, b, c = min(b, c) + ca, min(a, c) + cb, min(a, b) + cc

Breaking this down:

• New a (cost if current house is red): min(b, c) + ca

  • We take the minimum of the previous costs where the house was NOT red (either blue or green)
  • Add the cost of painting the current house red

• New b (cost if current house is blue): min(a, c) + cb

  • We take the minimum of the previous costs where the house was NOT blue (either red or green)
  • Add the cost of painting the current house blue

• New c (cost if current house is green): min(a, b) + cc

  • We take the minimum of the previous costs where the house was NOT green (either red or blue)
  • Add the cost of painting the current house green

The simultaneous assignment is crucial here - all three values are calculated using the old values before any updates occur.

Final Result: After processing all houses, a, b, and c contain the minimum costs to paint all houses with the last house being red, blue, or green respectively. The answer is the minimum among these three values:

return min(a, b, c)

Time Complexity: O(n) where n is the number of houses, as we iterate through the list once.

Space Complexity: O(1) as we only use three variables regardless of input size.

Example Walkthrough

Let's walk through a small example with 3 houses to illustrate the solution approach:

Input:

costs = [[17,2,17], [16,16,5], [14,3,19]]

Initial State:

• a = 0 (min cost if current house is red)
• b = 0 (min cost if current house is blue)
• c = 0 (min cost if current house is green)

House 0: [17, 2, 17]

• ca = 17, cb = 2, cc = 17
• New a = min(b, c) + ca = min(0, 0) + 17 = 17
• New b = min(a, c) + cb = min(0, 0) + 2 = 2
• New c = min(a, b) + cc = min(0, 0) + 17 = 17
• After House 0: a = 17, b = 2, c = 17
  • This means: painting house 0 red costs 17, blue costs 2, green costs 17

House 1: [16, 16, 5]

• ca = 16, cb = 16, cc = 5
• New a = min(b, c) + ca = min(2, 17) + 16 = 2 + 16 = 18
  • If we paint house 1 red, house 0 must be blue (cost 2) or green (cost 17), we choose blue
• New b = min(a, c) + cb = min(17, 17) + 16 = 17 + 16 = 33
  • If we paint house 1 blue, house 0 must be red (cost 17) or green (cost 17)
• New c = min(a, b) + cc = min(17, 2) + 5 = 2 + 5 = 7
  • If we paint house 1 green, house 0 must be red (cost 17) or blue (cost 2), we choose blue
• After House 1: a = 18, b = 33, c = 7

House 2: [14, 3, 19]

• ca = 14, cb = 3, cc = 19
• New a = min(b, c) + ca = min(33, 7) + 14 = 7 + 14 = 21
  • If we paint house 2 red, house 1 must be blue (total cost 33) or green (total cost 7), we choose green
• New b = min(a, c) + cb = min(18, 7) + 3 = 7 + 3 = 10
  • If we paint house 2 blue, house 1 must be red (total cost 18) or green (total cost 7), we choose green
• New c = min(a, b) + cc = min(18, 33) + 19 = 18 + 19 = 37
  • If we paint house 2 green, house 1 must be red (total cost 18) or blue (total cost 33), we choose red
• After House 2: a = 21, b = 10, c = 37

Final Result:

• min(a, b, c) = min(21, 10, 37) = 10

The optimal solution paints: House 0 blue (2) → House 1 green (5) → House 2 blue (3) = Total cost of 10.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of houses (length of the costs array). The algorithm iterates through the costs array exactly once, performing constant-time operations (comparisons and additions) for each house.

Space Complexity: O(1). The algorithm uses only three variables (a, b, c) to track the minimum costs regardless of the input size. The space usage remains constant as it doesn't create any additional data structures that scale with the input. The variables are reused and updated in each iteration rather than storing all intermediate results.

Common Pitfalls

1. Incorrect Variable Update Order

One of the most common mistakes is updating the variables sequentially instead of simultaneously, which leads to using already-updated values in subsequent calculations.

Incorrect Implementation:

# WRONG: Sequential updates use modified values
for ca, cb, cc in costs:
    a = min(b, c) + ca  # Updates a first
    b = min(a, c) + cb  # Uses the NEW value of a (incorrect!)
    c = min(a, b) + cc  # Uses NEW values of both a and b (incorrect!)

Why it's wrong: When calculating b, we need the OLD value of a (from the previous house), but sequential assignment gives us the NEW value of a (for the current house). This violates the constraint that adjacent houses can't have the same color.

Correct Solution:

# CORRECT: Simultaneous update preserves old values
for ca, cb, cc in costs:
    a, b, c = min(b, c) + ca, min(a, c) + cb, min(a, b) + cc

Or use temporary variables:

# CORRECT: Using temporary variables
for ca, cb, cc in costs:
    new_a = min(b, c) + ca
    new_b = min(a, c) + cb
    new_c = min(a, b) + cc
    a, b, c = new_a, new_b, new_c

2. Misunderstanding the State Representation

Another pitfall is misinterpreting what the variables represent. Some might think a, b, c represent cumulative costs for each color across all houses, rather than the minimum cost up to the current house IF the current house is painted with that specific color.

Incorrect Mental Model:

• Thinking a = total cost of all red houses
• Thinking b = total cost of all blue houses
• Thinking c = total cost of all green houses

Correct Understanding:

• a = minimum total cost to paint houses 0 to i, with house i painted red
• b = minimum total cost to paint houses 0 to i, with house i painted blue
• c = minimum total cost to paint houses 0 to i, with house i painted green

3. Edge Case Handling

Forgetting to handle the edge case where the input array is empty.

Vulnerable Code:

def minCost(self, costs: List[List[int]]) -> int:
    a = b = c = 0
    for ca, cb, cc in costs:
        a, b, c = min(b, c) + ca, min(a, c) + cb, min(a, b) + cc
    return min(a, b, c)  # Returns 0 for empty input, which is correct

While this implementation actually handles empty input correctly (returns 0), it's good practice to be explicit:

More Explicit Handling:

def minCost(self, costs: List[List[int]]) -> int:
    if not costs:
        return 0
  
    a = b = c = 0
    for ca, cb, cc in costs:
        a, b, c = min(b, c) + ca, min(a, c) + cb, min(a, b) + cc
    return min(a, b, c)