NUHMAN.com

Introduction

LeetCode 265: Paint House II is an extension of the previous problem Paint House (LeetCode 256). In this problem, there are n houses, and each can be painted with one of k colors, but no two adjacent houses can have the same color.

The goal is to minimize the total painting cost.

Problem Statement

Given an n x k cost matrix costs, where costs[i][j] is the cost of painting house i with color j, return the minimum cost to paint all the houses such that no two adjacent houses have the same color.

Constraints

• 1 <= n <= 100
• 1 <= k <= 20
• costs[i][j] is a non-negative integer

Examples

python

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
# Paint house 0 with color 0 (cost 1), house 1 with color 2 (cost 4) → total = 5

Input: costs = [[8]]
Output: 8

✅ Step-by-Step Solution

💡 Key Insight

If we use normal DP where we check all combinations of different colors for adjacent houses, the time complexity is O(n * k²).

To optimize, we track:

• The minimum cost from the previous row (min1)
• The second minimum cost (min2)
• The index of the minimum cost color (idx1)

This allows us to avoid the inner k loop by cleverly reusing the min1 or min2 depending on whether the color is the same as the previous min.

✅ Optimized Python Code

python

def minCostII(costs: list[list[int]]) -> int:
    if not costs:
        return 0

    n, k = len(costs), len(costs[0])
    prev_min1 = prev_min2 = 0
    prev_idx1 = -1

    for i in range(n):
        curr_min1 = curr_min2 = float('inf')
        curr_idx1 = -1

        for j in range(k):
            cost = costs[i][j]
            if j == prev_idx1:
                cost += prev_min2  # Avoid using same color as previous min
            else:
                cost += prev_min1

            # Update in place
            costs[i][j] = cost

            # Track min1, min2, and their indices
            if cost < curr_min1:
                curr_min2 = curr_min1
                curr_min1 = cost
                curr_idx1 = j
            elif cost < curr_min2:
                curr_min2 = cost

        prev_min1, prev_min2, prev_idx1 = curr_min1, curr_min2, curr_idx1

    return prev_min1

🔍 Explanation

• prev_min1: Minimum cost of painting previous house
• prev_min2: Second minimum cost (to use when current color matches previous min)
• prev_idx1: Index of the color with previous min cost

We iterate over each house and for each color compute the minimum possible cost without violating the adjacent color constraint, in O(k) time instead of O(k²).

⏱️ Time and Space Complexity

• Time Complexity: O(n * k) – One pass over all costs, no inner k² loop
• Space Complexity: O(1) – In-place updates

🧪 Example Walkthrough

Input: [[1,5,3],[2,9,4]]

• House 0 → Paint with color 0 (cost = 1), min1 = 1, idx1 = 0, min2 = 3
• House 1:
• Color 0 → use min2 = 3 → cost = 2 + 3 = 5
• Color 1 → use min1 = 1 → cost = 9 + 1 = 10
• Color 2 → use min1 = 1 → cost = 4 + 1 = 5
• → Final row: [5, 10, 5] → min = 5

✅ Conclusion

LeetCode 265: Paint House II is a great challenge in optimizing a dynamic programming problem by reducing redundant comparisons.

You learned:

• The naïve approach is O(n * k²)
• The optimized DP using min1, min2, and color index reduces it to O(n * k)