# LeetCode 265: Paint House II

## Problem Restatement

We are given `n` houses and `k` colors.

The painting cost is stored in:

```python
costs[i][j]
```

which means:

> Cost to paint house `i` using color `j`.

Adjacent houses cannot use the same color.

We need to return the minimum total painting cost.

Unlike LeetCode 256, the number of colors is not fixed to `3`.

The constraints are:

```python
1 <= n <= 100
1 <= k <= 20
```

The problem asks for the minimum total cost while ensuring neighboring houses have different colors. ([leetcode.com](https://leetcode.com/problems/paint-house-ii/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | `costs`, an `n x k` matrix |
| Output | Minimum painting cost |
| Rule | Adjacent houses cannot share a color |
| Colors | `k` possible colors |

Example function shape:

```python
def minCostII(costs: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
costs = [
    [1, 5, 3],
    [2, 9, 4]
]
```

Possible valid paint choices:

| House 0 | House 1 | Total |
|---|---|---|
| 0 | 1 | 10 |
| 0 | 2 | 5 |
| 1 | 0 | 7 |
| 1 | 2 | 9 |
| 2 | 0 | 5 |
| 2 | 1 | 12 |

The minimum cost is:

```python
5
```

Answer:

```python
5
```

Example 2:

```python
costs = [[1, 3]]
```

Only one house exists.

Choose the cheapest color.

Answer:

```python
1
```

## First Thought: Standard Dynamic Programming

Define:

```python
dp[i][j]
```

as:

> Minimum cost to paint houses `0..i` where house `i` uses color `j`.

Transition:

```python
dp[i][j] =
    costs[i][j] +
    min(dp[i - 1][c] for c != j)
```

This is correct.

But for every house and every color, we scan all previous colors.

That gives:

$$
O(nk^2)
$$

## Problem With Naive DP

The expensive step is:

```python
min(dp[i - 1][c] for c != j)
```

For each color `j`, we repeatedly search the previous row.

But most of the time we only need:

1. The smallest value from the previous row.
2. The second smallest value.

## Key Insight

Suppose the previous row is:

```python
[7, 2, 5, 9]
```

Then:

| Value | Color |
|---|---|
| Minimum | `2` at color `1` |
| Second minimum | `5` at color `2` |

Now consider computing the next row.

If the current color is not color `1`, then we can safely use the global minimum:

```python
2
```

But if the current color is color `1`, we cannot reuse the same color.

Then we must use the second minimum:

```python
5
```

So for each color:

| Case | Previous cost |
|---|---|
| Current color != previous min color | Use previous minimum |
| Current color == previous min color | Use previous second minimum |

This removes the inner scan.

## Algorithm

Maintain:

| Variable | Meaning |
|---|---|
| `min1` | Smallest DP value from previous row |
| `min2` | Second smallest DP value |
| `min1_color` | Color index of the smallest value |

For every house:

1. Compute the new DP values.
2. For each color:
   - If the color equals `min1_color`, use `min2`.
   - Otherwise use `min1`.
3. Add the current painting cost.
4. While computing the row, update the new smallest and second smallest values.

## Walkthrough

Use:

```python
costs = [
    [1, 5, 3],
    [2, 9, 4]
]
```

### House 0

Costs:

```python
[1, 5, 3]
```

Minimums:

| Value | Color |
|---|---|
| `1` | `0` |
| `3` | `2` |

So:

```python
min1 = 1
min2 = 3
min1_color = 0
```

### House 1

Color `0`:

Cannot reuse color `0`, so use `min2`.

```python
3 + 2 = 5
```

Color `1`:

Can use `min1`.

```python
1 + 9 = 10
```

Color `2`:

Can use `min1`.

```python
1 + 4 = 5
```

Final row:

```python
[5, 10, 5]
```

Answer:

```python
5
```

## Correctness

For each house `i` and color `j`, the optimal previous color must be some color different from `j`.

The previous row contains exactly two important values:

1. The global minimum.
2. The smallest value whose color differs from `j`.

If `j` is not the color of the global minimum, then the global minimum is the best valid previous choice.

If `j` equals the color of the global minimum, then the global minimum cannot be used because adjacent houses cannot share a color. In this case, the second minimum is the best valid previous choice.

Thus every transition computes exactly:

```python
costs[i][j] + minimum_valid_previous_cost
```

which matches the original DP recurrence.

Since every row is computed correctly from the previous row, the final minimum value is the minimum total painting cost.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(nk)` | Each house-color pair is processed once |
| Space | `O(k)` | Only one DP row is stored |

This improves over the naive:

$$
O(nk^2)
$$

solution.

## Implementation

```python
class Solution:
    def minCostII(self, costs: list[list[int]]) -> int:
        if not costs:
            return 0

        k = len(costs[0])

        dp = [0] * k

        for row in costs:
            new_dp = [0] * k

            min1 = float("inf")
            min2 = float("inf")
            min1_color = -1

            for color in range(k):
                value = dp[color]

                if value < min1:
                    min2 = min1
                    min1 = value
                    min1_color = color
                elif value < min2:
                    min2 = value

            for color in range(k):
                if color == min1_color:
                    new_dp[color] = row[color] + min2
                else:
                    new_dp[color] = row[color] + min1

            dp = new_dp

        return min(dp)
```

## Code Explanation

We store the previous DP row in:

```python
dp = [0] * k
```

For every house:

```python
for row in costs:
```

we first find:

- smallest DP value
- second smallest DP value
- color index of the smallest value

```python
if value < min1:
```

updates the smallest value.

```python
elif value < min2:
```

updates the second smallest value.

Then compute the next row.

If the current color equals the minimum color:

```python
if color == min1_color:
```

we must avoid reusing that color, so we use `min2`.

Otherwise we use `min1`.

Finally:

```python
dp = new_dp
```

moves to the next house.

The answer is the minimum value in the final DP row.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minCostII([[1, 5, 3], [2, 9, 4]]) == 5
    assert s.minCostII([[1, 3]]) == 1
    assert s.minCostII([[8]]) == 8
    assert s.minCostII([
        [1, 2, 3],
        [1, 4, 6],
    ]) == 3

    assert s.minCostII([
        [7, 6, 2],
        [5, 8, 7],
        [3, 6, 1],
        [2, 4, 9],
    ]) == 14

    assert s.minCostII([
        [10, 3, 1, 8],
        [5, 7, 2, 9],
        [8, 1, 4, 3],
    ]) == 6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official example | Standard DP transition |
| Single house | Minimum single-row value |
| Single color | Trivial edge case |
| Small two-row case | Confirms color exclusion |
| Multi-row example | General correctness |
| Four-color example | Confirms generalized `k` handling |