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

What Is LeetCode 265: Paint House II?

In LeetCode 265: Paint House II, you’re given an n x k matrix costs, where costs[i][j] is the cost to paint house i with color j. Your goal is to find the minimum total cost to paint all n houses, with k color options per house, ensuring no two adjacent houses have the same color. For example, with costs = [[1,5,3], [2,9,4]], the minimum cost is 5 (paint house 0 with color 0 for 1, house 1 with color 2 for 4).

Problem Statement

• Input: An n x k integer matrix costs.
• Output: An integer—the minimum cost to paint all houses.
• Rules:
• Each house must be painted with one of k colors.
• No adjacent houses can have the same color.
• Minimize the total cost.

Constraints

• costs.length == n
• costs[i].length == k
• 1 <= n <= 100
• 2 <= k <= 20
• 1 <= costs[i][j] <= 20

Examples

• Input: costs = [[1,5,3], [2,9,4]]
• Output: 5
• Why: House 0: color 0 (1), House 1: color 2 (4), total = 5.
• Input: costs = [[1,3], [2,4]]
• Output: 5
• Why: House 0: color 0 (1), House 1: color 1 (4), total = 5.
• Input: costs = [[1]]
• Output: 1
• Why: Single house, single color.

Understanding the Problem: Painting with Constraints

To solve LeetCode 265: Paint House II in Python, we need to minimize the cost of painting n houses with k colors each, ensuring adjacent houses differ in color. A naive approach—trying all combinations—would take O(k^n) time, which is infeasible for n up to 100 and k up to 20. Instead, we’ll use dynamic programming to build the solution efficiently:

• Best Solution (DP with O(1) Space): O(n*k) time, O(1) space—tracks min costs in-place.
• **Alternative Solution (DP with O(n*k) Space)**: O(n*k) time, O(n*k) space—uses a full DP table.

Let’s dive into the Best Solution—DP with O(1) space—and break it down step-by-step.

Best Solution: Dynamic Programming with O(1) Space

Why This Is the Best Solution

The DP with O(1) space approach is the top choice because it’s both time-efficient—O(n*k)—and space-efficient—O(1) extra space beyond the input—while being cleverly optimized. It modifies the input costs array in-place, tracking the minimum and second-minimum costs from the previous row to avoid recalculating, ensuring the no-adjacent-same-color rule. It’s like painting house by house, keeping a mental note of the cheapest options so far—smart and lean!

How It Works

Here’s the strategy:

• Step 1: Handle Edge Cases:
• Empty or single-house cases.
• Step 2: Iterate Rows:
• For each house (row):
• Track previous row’s min cost (prev_min) and its color (prev_min_color).
• Track second-min cost (prev_second_min) for when min color is excluded.
• Update current row’s costs by adding the min cost from the previous row, excluding same-color conflicts.
• Step 3: Final Min:
• Return the minimum cost in the last row.

Step-by-Step Example

Example: costs = [[1,5,3], [2,9,4]]

• Initial Costs:

1 5 3 (House 0) 2 9 4 (House 1)

• House 0 (Row 0):
• No previous row, use as is.
• prev_min = 1, prev_min_color = 0, prev_second_min = 3.
• House 1 (Row 1):
• For color 0: 2 + (not 0, so prev_second_min = 3) = 5.
• For color 1: 9 + (prev_min = 1) = 10.
• For color 2: 4 + (prev_min = 1) = 5.
• Update: costs[1] = [5, 10, 5].
• New prev_min = 5, prev_min_color = 0 (or 2), prev_second_min = 5.
• Result: min(costs[1]) = 5.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        # Step 1: Handle edge cases
        if not costs:
            return 0
        if len(costs) == 1:
            return min(costs[0])

        n, k = len(costs), len(costs[0])

        # Step 2: Iterate through houses
        prev_min = 0
        prev_min_color = -1
        prev_second_min = 0

        for i in range(n):
            curr_min = float('inf')
            curr_min_color = -1
            curr_second_min = float('inf')

            # Find min and second min from previous row
            for j in range(k):
                if i == 0:
                    cost = costs[0][j]
                else:
                    cost = costs[i][j] + (prev_second_min if j == prev_min_color else prev_min)
                if cost < curr_min:
                    curr_second_min = curr_min
                    curr_min = cost
                    curr_min_color = j
                elif cost < curr_second_min:
                    curr_second_min = cost

            # Update costs in-place for next iteration
            if i < n - 1:
                for j in range(k):
                    costs[i + 1][j] += (curr_second_min if j == curr_min_color else curr_min)

            prev_min = curr_min
            prev_min_color = curr_min_color
            prev_second_min = curr_second_min

        # Step 3: Return min cost from last row
        return prev_min

• Line 4-7: Handle empty or single-house cases.
• Line 9: Get dimensions.
• Line 12-15: Initialize previous row trackers.
• Line 18-36: Process each house:
• Line 22-30: Compute current costs, track min and second min.
• Line 33-35: Update next row in-place (if not last).
• Line 37-39: Update previous trackers.
• Line 42: Return final min cost.
• Time Complexity: O(n*k)—each cell processed once.
• Space Complexity: O(1)—only a few variables.

This is a cost-painting wizard!

Alternative Solution: Dynamic Programming with O(n*k) Space

Why an Alternative Approach?

The DP with O(nk) space approach offers a clearer, more traditional take—O(nk) time, O(n*k) space—using a full DP table to store minimum costs for each house and color combination. It’s easier to understand but uses more space. It’s like keeping a ledger of all possible painting costs, picking the cheapest path—systematic and explicit!

How It Works

• Step 1: Build DP table: dp[i][j] is min cost to paint houses 0 to i with house i using color j.
• Step 2: Fill table, ensuring no adjacent same colors.
• Step 3: Return min of last row.

Step-by-Step Example

Example: costs = [[1,5,3], [2,9,4]]

• DP Table:

1 5 3 (House 0) 5 10 5 (House 1)

• House 0: dp[0] = [1, 5, 3].
• House 1:
• Color 0: 2 + min(5, 3) = 5.
• Color 1: 9 + min(1, 3) = 10.
• Color 2: 4 + min(1, 5) = 5.
• Result: min(dp[1]) = 5.

Code for DP Approach

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        if not costs:
            return 0
        if len(costs) == 1:
            return min(costs[0])

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

        # Step 1: First row
        for j in range(k):
            dp[0][j] = costs[0][j]

        # Step 2: Fill DP table
        for i in range(1, n):
            for j in range(k):
                min_prev = float('inf')
                for prev_color in range(k):
                    if prev_color != j:
                        min_prev = min(min_prev, dp[i-1][prev_color])
                dp[i][j] = costs[i][j] + min_prev

        # Step 3: Return min of last row
        return min(dp[n-1])

• Line 10-12: First row from costs.
• Line 15-21: Fill DP, exclude same color.
• Time Complexity: O(n*k²)—k checks per cell.
• Space Complexity: O(n*k)—DP table.

It’s a full-table cost tracker!

Comparing the Two Solutions

• DP O(1) Space (Best):
• Pros: O(n*k) time, O(1) space, fast and lean.
• Cons: Modifies input, less intuitive.
• **DP O(n*k) Space (Alternative)**:
• Pros: O(n*k²) time, O(n*k) space, clear and explicit.
• Cons: Slower, more space.

O(1) space wins for efficiency.

Additional Examples and Edge Cases

• [[8]]: 8.
• [[1,2], [3,4]]: 4.
• [[1,5,3]]: 1.

Both handle these well.

Complexity Breakdown

• O(1) Space: Time O(n*k), Space O(1).
• **O(n*k) Space**: Time O(n*k²), Space O(n*k).

O(1) space’s speed shines.

Key Takeaways

• O(1) Space: Min tracking rocks!
• **O(n*k) Space**: Table it out!
• Constraints: Adjacent colors matter.
• Python Tip: In-place saves space—see [Python Basics](/python/basics).

Final Thoughts: Paint Smart

LeetCode 265: Paint House II in Python is a cost-minimizing challenge. The O(1) space DP paints with precision, while O(nk) space offers clarity. Want more DP fun? Try LeetCode 256: Paint House or LeetCode 198: House Robber. Ready to paint? Head to Solve LeetCode 265 on LeetCode* and minimize that cost today!