LeetCode 256: Paint House - Complete Solutions Guide

Problem Statement

There are a row of n houses, each house can be painted with one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You need to paint all the houses such that no two adjacent houses have the same color, and calculate the minimum cost to paint all houses.

Copy codeInput: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 blue (2), house 1 green (5), house 2 blue (3)
Total cost: 2 + 5 + 3 = 10

Solution 1: Recursive with Memoization

Explanation

This top-down approach recursively explores all valid color choices while memoizing results to avoid recomputation: 1. Base Case: No houses left to paint (cost = 0) 2. Recursive Case: For each house, try all colors different from previous 3. Memoization: Store computed results to optimize

Step-by-Step Example

For costs = [[17,2,17],[16,16,5],[14,3,19]]: 1. Start with house 0, choose color 1 (cost=2) 2. For house 1, choose color 2 (different from color 1) 3. For house 2, choose color 1 (different from color 2) 4. Total cost = 2 + 5 + 3 = 10

Python Code

Copy codeclass Solution:
    def minCost(self, costs: list[list[int]]) -> int:
        if not costs:
            return 0

        memo = {}

        def dp(house, prev_color):
            if house == len(costs):
                return 0
            if (house, prev_color) in memo:
                return memo[(house, prev_color)]

            min_cost = float('inf')
            for color in range(3):
                if color != prev_color:
                    current_cost = costs[house][color] + dp(house + 1, color)
                    min_cost = min(min_cost, current_cost)

            memo[(house, prev_color)] = min_cost
            return min_cost

        return dp(0, -1)

Complexity

• Time: O(n) - Each subproblem solved once
• Space: O(n) - Memoization storage and recursion stack
• Pros: Intuitive recursive logic

Solution 2: Dynamic Programming (Optimal)

Explanation

This bottom-up approach builds the solution iteratively: 1. DP Table: dp[i][j] = min cost to paint house i with color j 2. Transition: dp[i][j] = costs[i][j] + min(dp[i-1][k] for k != j) 3. Result: Minimum of last row in DP table

Python Code

Copy codeclass Solution:
    def minCost(self, costs: list[list[int]]) -> int:
        if not costs:
            return 0

        n = len(costs)
        dp = [[0] * 3 for _ in range(n)]
        dp[0] = costs[0]

        for i in range(1, n):
            dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
            dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
            dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

        return min(dp[-1])

Complexity

• Time: O(n) - Single pass through houses
• Space: O(n) - DP table storage
• Why Best: Efficient and straightforward implementation

Solution 3: Space-Optimized DP

Explanation

Optimize space by reusing variables since we only need previous house's costs: 1. Track Costs: Maintain three variables for previous house's color costs 2. Update Iteratively: Compute current house costs based on previous 3. No Full Table: Only store necessary information

Python Code

Copy codeclass Solution:
    def minCost(self, costs: list[list[int]]) -> int:
        if not costs:
            return 0

        prev_red, prev_blue, prev_green = costs[0]

        for i in range(1, len(costs)):
            curr_red = costs[i][0] + min(prev_blue, prev_green)
            curr_blue = costs[i][1] + min(prev_red, prev_green)
            curr_green = costs[i][2] + min(prev_red, prev_blue)

            prev_red, prev_blue, prev_green = curr_red, curr_blue, curr_green

        return min(prev_red, prev_blue, prev_green)

Complexity

• Time: O(n) - Same as regular DP
• Space: O(1) - Constant space usage
• Pros: Most space-efficient solution

Edge Cases to Consider

1. Single house: Return minimum of its three costs
2. Two houses: Choose different colors with minimum sum
3. All same costs: Any valid coloring will work
4. Large n: Ensure solution works within constraints
5. Extreme costs: Handle minimum/maximum cost values

Final Thoughts

• Interview Tip: Space-optimized DP is preferred
• Key Insight: Current choice only depends on previous choice
• Follow-up: How would you handle k colors instead of 3?