Paint House II

50 min · minCostII()

The paint catalog just grew from three colors to k. Your choices are wider, but the same neighbor rule can turn a cheap-looking color into an expensive mistake.

You're given a matrix, a grid of rows and columns, named costs. costs[i][color] is the price of painting house i with that color. Every row has the same k color columns.

Choose one color for every house and return the smallest possible total cost.

A few ground rules:

Adjacent houses are neighbors whose indices differ by one. They can't share a color.
Every house must receive exactly one color.
When the street has more than one house, at least two colors are available.

Constraints

1 <= costs.length <= 100
1 <= k <= 20
Every row in costs contains exactly k integers.
0 <= costs[i][color] <= 1_000
If costs.length > 1, then k >= 2.

Hints

Start with the direct transition

For each color at the current house, scan every different color from the previous house and extend the cheapest total you find.

Notice the repeated search

Every current color asks almost the same question: what's the smallest previous total, excluding my own color? Most colors can use one shared minimum.

Keep two winners

Record the smallest previous total, its color, and the second-smallest total. Use the second-smallest only when the current color matches the smallest total's color.

Follow-up

Could you return the chosen color for every house as well as the minimum cost? What extra history would you need to reconstruct that plan?

Visible cases

Examples

Example 1

ready

Input: costs = [ [ 1, 5, 3 ], [ 2, 9, 4 ] ]
Expected: 5
Why: red then green, or green then red, costs 5

Example 2

ready

Input: costs = [ [ 8, 3, 5, 1 ] ]
Expected: 1
Why: one house can take its cheapest color

Example 3

ready

Input: costs = [ [ 1, 10 ], [ 10, 1 ], [ 1, 10 ] ]
Expected: 3
Why: with two colors, the valid plan alternates

Interview signal

Asked at

AmazonGoogle

Scan every previous color

Dynamic programming (DP) stores the best answer for each smaller state so later states can reuse it. After processing one house, let previous[color] hold the cheapest valid total whose latest house uses color.

For every color in the next row, scan all different previous colors and extend the cheapest one. This bottom-up DP is direct and hard to get wrong.

def min_cost_ii(costs: list[list[int]]) -> int:
    previous = costs[0][:]
    k = len(previous)
 
    for row in costs[1:]:
        current: list[int] = []
        for color, paint_cost in enumerate(row):
            best_previous = min(
                previous[other]
                for other in range(k)
                if other != color
            )
            current.append(paint_cost + best_previous)
        previous = current
 
    return min(previous)

There are n · k states, and each transition scans up to k - 1 previous colors.

Time O(n · k²). Space O(k) for the previous and current rows.

Two-minimum rolling DP

The inner scan asks for the smallest previous total that doesn't use the current color. You can answer every one of those queries after finding just three facts:

the smallest previous total,
the color that owns it, and
the second-smallest previous total.

If the current color differs from the smallest total's color, extend the smallest. If the colors match, extend the second-smallest instead. Equal minima work too: one becomes the smallest and the other becomes the second-smallest.

def min_cost_ii(costs: list[list[int]]) -> int:
    previous = costs[0][:]
 
    for row in costs[1:]:
        smallest = float("inf")
        second_smallest = float("inf")
        smallest_color = -1
 
        for color, total in enumerate(previous):
            if total < smallest:
                second_smallest = smallest
                smallest = total
                smallest_color = color
            elif total < second_smallest:
                second_smallest = total
 
        current: list[int] = []
        for color, paint_cost in enumerate(row):
            prior = second_smallest if color == smallest_color else smallest
            current.append(paint_cost + prior)
        previous = current
 
    return min(previous)

Each row now needs one scan to find the two minima and one scan to build the next DP row. No color starts another scan of all k choices.

Time O(n · k). Space O(k) for the rolling row.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraycosts: int[][]

Expected

Run: visible + custom · Submit: full suite