LeetCode 256: Paint House Solution in Python – A Step-by-Step Guide

What Is LeetCode 256: Paint House?

In LeetCode 256: Paint House, you’re given a 2D list costs where each row represents a house, and each column shows the cost to paint that house red, blue, or green. Your goal is to calculate the minimum total cost to paint all houses, with the catch that no two adjacent houses can have the same color. This problem introduces dynamic programming in a practical way, similar to challenges like LeetCode 198: House Robber, but with a colorful twist.

Problem Statement

• Input: A 2D list costs where costs[i][j] is the cost to paint house i with color j (0 = red, 1 = blue, 2 = green).
• Output: An integer—the minimum total cost to paint all houses.
• Rules: Adjacent houses must have different colors; choose from three colors per house.

Constraints

• Number of houses: 0 to 100.
• Costs: 0 to 1000.
• costs[i].length == 3 (three color options per house).

Examples

• Input: costs = [[17,2,17], [16,16,5], [14,3,19]]
• Output: 10 (paint house 0 blue (2), house 1 green (5), house 2 blue (3) = 2 + 5 + 3 = 10).
• Input: costs = []
• Output: 0 (no houses, no cost).
• Input: costs = [[7,6,2]]
• Output: 2 (one house, cheapest color is green at 2).

Understanding the Problem: Painting with Rules

To solve LeetCode 256: Paint House in Python, we need to pick a color for each house—red, blue, or green—while keeping neighbors different and the total cost as low as possible. The 2D list gives us costs like this:

• costs[0][0] = cost to paint house 0 red.
• costs[0][1] = cost to paint house 0 blue.
• costs[0][2] = cost to paint house 0 green.

A simple way—trying every combination—works but takes too long. We’ll use two methods: 1. Best Solution (Dynamic Programming with In-Place): O(n) time—quick and clever. 2. Alternative Solution (Brute Force Recursion): O(3^n) time—easy to picture but slow.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Dynamic Programming with In-Place Modification

Why This Is the Best Solution

The dynamic programming approach that updates costs in place is the top pick for LeetCode 256 because it solves the problem in O(n) time—where n is the number of houses—and uses almost no extra space. It builds the answer house by house, keeping track of the cheapest way to paint up to each point, making it both fast and memory-friendly.

How It Works

Picture yourself painting houses one by one, standing at each house and asking, “What’s the cheapest way to paint everything up to here, considering I can’t match the next house’s color?” You use the costs from the previous house to figure out the best option for the current one, tweaking the numbers as you go. Here’s how it works, step-by-step, explained in a way that’s easy to follow:

• Step 1: Start with the First House:
• For house 0, the cost is just what’s given—no neighbors to worry about yet.
• Example: [17, 2, 17] means red = 17, blue = 2, green = 17.
• Step 2: Move to the Next House:
• For house 1, you can’t use the same color as house 0. So, for each color at house 1, add the cheapest cost from house 0 that uses a different color.
• Example: House 1 costs [16, 16, 5]:
• Red (16) + min(blue 2, green 17) = 16 + 2 = 18.
• Blue (16) + min(red 17, green 17) = 16 + 17 = 33.
• Green (5) + min(red 17, blue 2) = 5 + 2 = 7.
• Update house 1’s costs to [18, 33, 7]—these now include the best way to reach house 1 with each color.
• Step 3: Keep Going:
• For each house after that, update its costs by adding the minimum from the previous house’s other two colors.
• It’s like saying, “If I paint this house red, what’s the cheapest way to paint all before it without ending in red?”
• Step 4: Finish Up:
• At the last house, the updated costs show the total minimum cost to paint everything, ending with each color. Pick the smallest one.
• Step 5: Edge Cases:
• No houses? Cost is 0.
• One house? Pick the cheapest color.

It’s like building a cost ladder: each step adds the best previous choice, skipping the color you’re using now!

Step-by-Step Example

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

• Step 1: House 0:
• Costs stay [17, 2, 17] (no previous house).
• Step 2: House 1:
• Original: [16, 16, 5].
• Update with house 0 [17, 2, 17]:
• Red: 16 + min(2, 17) = 16 + 2 = 18.
• Blue: 16 + min(17, 17) = 16 + 17 = 33.
• Green: 5 + min(17, 2) = 5 + 2 = 7.
• New costs: [18, 33, 7].
• Step 3: House 2:
• Original: [14, 3, 19].
• Update with house 1 [18, 33, 7]:
• Red: 14 + min(33, 7) = 14 + 7 = 21.
• Blue: 3 + min(18, 7) = 3 + 7 = 10.
• Green: 19 + min(18, 33) = 19 + 18 = 37.
• New costs: [21, 10, 37].
• Step 4: Find Minimum:
• Min of [21, 10, 37] = 10.
• Result: 10.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        # Step 1: Check if there are no houses
        if not costs:
            return 0

        # Step 2: Start with the first house
        # No need to change it yet—it’s our starting point
        n = len(costs)  # Number of houses

        # Step 3: Update costs for each house after the first
        for i in range(1, n):
            # For each color at the current house
            # Add the cheapest cost from the previous house’s other colors
            prev = costs[i-1]  # Previous house’s costs
            curr = costs[i]    # Current house’s original costs

            # Red: Add min of previous blue or green
            costs[i][0] = curr[0] + min(prev[1], prev[2])
            # Blue: Add min of previous red or green
            costs[i][1] = curr[1] + min(prev[0], prev[2])
            # Green: Add min of previous red or blue
            costs[i][2] = curr[2] + min(prev[0], prev[1])

        # Step 4: Get the smallest total cost from the last house
        return min(costs[-1])

• Time Complexity: O(n)—we visit each house once, and each has 3 colors.
• Space Complexity: O(1)—we update the input list, no extra space.

This solution is like painting smartly—each step picks the best deal from before!

Alternative Solution: Brute Force with Recursion

Why an Alternative Approach?

The brute force recursion method tries every possible color combination, like testing all ways to paint the houses and picking the cheapest. It’s slower but helps you see the problem’s full picture, making it a nice way to start thinking about the challenge.

How It Works

Imagine you’re standing at house 0, trying red, blue, or green, then moving to house 1 and trying all three again, but skipping the color you just used. You keep going until you’ve painted everything, then add up the costs. Here’s how it works, step-by-step:

• Step 1: Start at House 0:
• Try each color and move to the next house.
• Step 2: Recurse with Rules:
• For each house, pick a color different from the previous one.
• Add its cost and keep going.
• Step 3: Track Costs:
• When you reach the end, save the total cost and find the smallest.

It’s like playing a game of “what if”—trying every path to see which one’s cheapest!

Step-by-Step Example

Example: costs = [[17,2,17], [16,16,5]]

• House 0:
• Red (17): House 1 → Blue (16) = 33, Green (5) = 22.
• Blue (2): House 1 → Red (16) = 18, Green (5) = 7.
• Green (17): House 1 → Red (16) = 33, Blue (16) = 33.
• Totals: [33, 22, 18, 7, 33, 33].
• Result: Min = 7.

Code for Brute Force Approach

Copy codeclass Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        # Step 1: Handle no houses
        if not costs:
            return 0

        # Step 2: Helper function to try colors
        def paint(house, prev_color):
            # If we’ve painted all houses
            if house == len(costs):
                return 0

            # Try each color for this house
            min_cost = float('inf')
            for color in range(3):
                if color != prev_color:  # Can’t match previous
                    cost = costs[house][color] + paint(house + 1, color)
                    min_cost = min(min_cost, cost)
            return min_cost

        # Step 3: Start from house 0 with no previous color
        return paint(0, -1)

• Time Complexity: O(3^n)—exponential, trying all combinations.
• Space Complexity: O(n)—recursion stack.

It’s thorough but takes time.

Comparing the Two Solutions

• Best Solution (DP):
• Pros: O(n) time, O(1) space, fast.
• Cons: Needs a bit of planning.
• Alternative Solution (Recursion):
• Pros: Shows all possibilities.
• Cons: O(3^n) time, slow for many houses.

DP wins for efficiency.

Additional Examples and Edge Cases

Single House

• [[1,2,3]] → 1

No Houses

• [] → 0

Two Houses

• [[1,2,3], [1,2,3]] → 2

Both work well here.

Complexity Breakdown

• DP:
• Time: O(n)—linear pass.
• Space: O(1)—in-place.
• Recursion:
• Time: O(3^n)—exponential.
• Space: O(n)—stack.

DP is the clear winner.

Key Takeaways

• Dynamic Programming: Build answers step-by-step.
• Rules Matter: Skip neighbor colors cleverly.
• Recursion: Try everything—great for understanding.
• Python Tip: Lists can be updated—see [Python Basics](/python/basics).

Final Thoughts: Paint Smartly

LeetCode 256: Paint House in Python is a colorful coding adventure. The DP solution keeps costs low and fast, while recursion explores every option. Want more? Try LeetCode 198: House Robber or LeetCode 265: Paint House II. Ready to paint? Head to Solve LeetCode 256 on LeetCode and color those houses today!