1. Memoization

Intuition

This is a generalization of the Paint House problem where we now have k colors instead of just 3. The core constraint remains the same: no two adjacent houses can have the same color.

We recursively try each valid color for the current house and find the minimum cost to paint all remaining houses. Since the same subproblems are solved multiple times, we use memoization to cache results.

Algorithm

  1. Define a recursive function memoSolve(houseNumber, color) that returns the minimum cost to paint from the current house to the end, given that the current house is painted with the specified color.
  2. Base case: If at the last house, return the cost of painting it with the given color.
  3. For each valid color choice for the next house (any color except the current one), recursively compute the minimum remaining cost.
  4. Cache the result for each (houseNumber, color) pair to avoid recomputation.
  5. Try all colors for house 0 and return the minimum total cost.
from functools import lru_cache

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        # Start by defining n and k to make the following code cleaner.
        n = len(costs)
        if n == 0: return 0 # No houses is a valid test case!
        k = len(costs[0])

        # If you're not familiar with lru_cache, look it up in the docs as it's
        # essential to know about.
        @lru_cache(maxsize=None)
        def memo_solve(house_num, color):

            # Base case.
            if house_num == n - 1:
                return costs[house_num][color]

            # Recursive case.
            cost = math.inf
            for next_color in range(k):
                if next_color == color:
                    continue # Can't paint adjacent houses the same color!
                cost = min(cost, memo_solve(house_num + 1, next_color))
            return costs[house_num][color] + cost

        # Consider all options for painting house 0 and find the minimum.
        cost = math.inf
        for color in range(k):
            cost = min(cost, memo_solve(0, color))
        return cost

Time & Space Complexity

  • Time complexity: O(n⋅k2)O(n \cdot k^2)

  • Space complexity: O(n⋅k)O(n \cdot k)

Where nn is the number of houses in a row, and kk is the number of colors available for painting.

2. Dynamic Programming

Intuition

We can solve this iteratively by building up the minimum costs house by house. For each house and each color, we need the minimum cost from the previous house excluding that same color.

The straightforward approach checks all k colors from the previous row to find the minimum, giving O(k) work per cell and O(n * k^2) overall.

Algorithm

  1. Process houses from index 1 to n-1. For house 0, the costs are just the given painting costs.
  2. For each house and each color, find the minimum cost among all different colors from the previous house.
  3. Add this minimum to the current painting cost and update the costs array in place.
  4. After processing all houses, return the minimum value in the last row.
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:

        n = len(costs)
        if n == 0: return 0
        k = len(costs[0])

        for house in range(1, n):
            for color in range(k):
                best = math.inf
                for previous_color in range(k):
                    if color == previous_color: continue
                    best = min(best, costs[house - 1][previous_color])
                costs[house][color] += best

        return min(costs[-1])

Time & Space Complexity

  • Time complexity: O(n⋅k2)O(n \cdot k^2)

  • Space complexity: O(1)O(1) if done in-place, O(n⋅k)O(n \cdot k) if input is copied.

Where nn is the number of houses in a row, and kk is the number of colors available for painting.

3. Dynamic Programming with O(k) additional Space

Intuition

The previous solution modifies the input array. If we want to preserve it, we can use a separate array of size k to track the costs from the previous row.

This approach maintains the same logic but uses an auxiliary array instead of modifying the input directly.

Algorithm

  1. Copy the first row of costs into previousRow.
  2. For each subsequent house, create a new currentRow array.
  3. For each color, find the minimum value in previousRow excluding the same color index, and add the current painting cost.
  4. After processing each house, set previousRow = currentRow.
  5. Return the minimum value in the final previousRow.
def minCostII(self, costs: List[List[int]]) -> int:

    n = len(costs)
    if n == 0: return 0
    k = len(costs[0])

    previous_row = costs[0]

    for house in range(1, n):
        current_row = [0] * k
        for color in range(k):
            best = math.inf
            for previous_color in range(k):
                if color == previous_color: continue
                best = min(best, previous_row[previous_color])
            current_row[color] += costs[house][color] + best
        previous_row = current_row

    return min(previous_row)

Time & Space Complexity

  • Time complexity: O(n⋅k2)O(n \cdot k^2)

  • Space complexity: O(k)O(k)

Where nn is the number of houses in a row, and kk is the number of colors available for painting.

4. Dynamic programming with Optimized Time

Intuition

The O(k^2) time per house comes from finding the minimum in the previous row for each color. But notice: for all colors except one, we just need the global minimum of the previous row. The exception is when the current color matches the minimum color from the previous row, in which case we need the second minimum.

By precomputing the minimum and second minimum colors from each row, we can update each cell in O(1) time, reducing the overall complexity to O(n * k).

Algorithm

  1. For each house (starting from index 1), first find the indices of the minimum and second minimum costs in the previous row.
  2. For each color in the current row:
    • If this color matches the minimum color from the previous row, add the second minimum cost.
    • Otherwise, add the minimum cost.
  3. Repeat until all houses are processed.
  4. Return the minimum value in the final row.
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:

        n = len(costs)
        if n == 0: return 0
        k = len(costs[0])

        for house in range(1, n):
            # Find the colors with the minimum and second to minimum
            # in the previous row.
            min_color = second_min_color = None
            for color in range(k):
                cost = costs[house - 1][color]
                if min_color is None or cost < costs[house - 1][min_color]:
                    second_min_color = min_color
                    min_color = color
                elif second_min_color is None or cost < costs[house - 1][second_min_color]:
                    second_min_color = color
            # And now update the costs for the current row.
            for color in range(k):
                if color == min_color:
                    costs[house][color] += costs[house - 1][second_min_color]
                else:
                    costs[house][color] += costs[house - 1][min_color]

        # The answer will now be the minimum of the last row.
        return min(costs[-1])

Time & Space Complexity

  • Time complexity: O(n⋅k)O(n \cdot k)

  • Space complexity: O(1)O(1)

Where nn is the number of houses in a row, and kk is the number of colors available for painting.

5. Dynamic programming with Optimized Time and Space

Intuition

Building on the previous optimization, we realize we do not actually need to store the entire previous row. We only need three pieces of information: the minimum cost, the second minimum cost, and which color achieved the minimum.

By tracking just these three values as we process each house, we can compute everything in O(1) space while maintaining O(n * k) time complexity.

Algorithm

  1. Initialize by finding the minimum cost, second minimum cost, and minimum color index from the first row.
  2. For each subsequent house, iterate through all colors:
    • If the current color equals the previous minimum color, the cost is current_cost + prev_second_min.
    • Otherwise, the cost is current_cost + prev_min.
  3. Track the new minimum, second minimum, and minimum color as you process each color.
  4. After processing all houses, the final minimum cost is the answer.
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n = len(costs)
        if n == 0: return 0 # This is a valid case.
        k = len(costs[0])

        # Firstly, we need to determine the 2 lowest costs of
        # the first row. We also need to remember the color of
        # the lowest.
        prev_min_cost = prev_second_min_cost = prev_min_color = None
        for color, cost in enumerate(costs[0]):
            if prev_min_cost is None or cost < prev_min_cost:
                prev_second_min_cost = prev_min_cost
                prev_min_color = color
                prev_min_cost = cost
            elif prev_second_min_cost is None or cost < prev_second_min_cost:
                prev_second_min_cost = cost

        # And now, we need to work our way down, keeping track of the minimums.
        for house in range(1, n):
            min_cost = second_min_cost = min_color = None
            for color in range(k):
                # Determime cost for this cell (without writing it into input array.)
                cost = costs[house][color]
                if color == prev_min_color:
                    cost += prev_second_min_cost
                else:
                    cost += prev_min_cost
                # And work out whether or not it is a current minimum.
                if min_cost is None or cost < min_cost:
                    second_min_cost = min_cost
                    min_color = color
                    min_cost = cost
                elif second_min_cost is None or cost < second_min_cost:
                    second_min_cost = cost
            # Transfer currents to be prevs.
            prev_min_cost = min_cost
            prev_min_color = min_color
            prev_second_min_cost = second_min_cost

        return prev_min_cost

Time & Space Complexity

  • Time complexity: O(n⋅k)O(n \cdot k)

  • Space complexity: O(1)O(1)

Where nn is the number of houses in a row, and kk is the number of colors available for painting.

Common Pitfalls

Using O(k^2) Time Per House Without Optimization

The naive approach of checking all k colors from the previous row for each of k colors in the current row results in O(n*k^2) time. For large k values, this times out. The key insight is that you only need to track the minimum and second minimum costs from the previous row, reducing per-house work to O(k).

Not Handling the Case When k Equals 1

When there is only one color available, it is impossible to paint more than one house without violating the adjacent color constraint. Some implementations crash or return incorrect results because they assume k >= 2. Always check if k equals 1 and n > 1, returning an error indicator or handling it appropriately.

Forgetting to Track Which Color Achieved the Minimum

When optimizing with minimum and second minimum tracking, you must remember which color index gave the minimum cost. Without this, you cannot determine whether to use the minimum or second minimum when processing the next row, since you need the second minimum only when the current color matches the previous minimum color.

Modifying the Input Array Unexpectedly

Some solutions modify the costs array in place to save space. While this works, it can cause issues if the caller expects the original data to remain unchanged. Either document this behavior clearly, work on a copy of the input, or use the O(1) space solution that tracks only the necessary values without modifying input.

Off-by-One Errors in House Indexing

The DP processes houses from index 1 to n-1, using costs from house 0 as the base case. Confusing 0-indexed and 1-indexed loops, or incorrectly referencing costs[house-1] versus costs[house], leads to accessing wrong cost values or array out-of-bounds errors.