# How to Solve the Paint House II Problem Using Dynamic Programming

> Solve the Paint House II problem efficiently with dynamic programming. Discover the O(nk) time and O(1) space solution by tracking minimum costs. Learn the optimal approach now.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: tutorial
- Published: 2026-03-04

---

**The Paint House II problem can be solved in O(n·k) time and O(1) extra space by tracking the two minimum costs from the previous house and using them to compute current costs without scanning all k colors for each house.**

The Paint House II problem is a classic dynamic programming challenge that extends the original Paint House problem by allowing k colors instead of just three. This article explains the optimal O(n·k) solution implemented in the **kdn251/interviews** repository, where the algorithm reuses the input cost matrix to store intermediate DP values while tracking only the two smallest costs from the previous row.

## Understanding the Paint House II Problem

The problem asks for the minimum total cost to paint a row of n houses, where each house can be painted one of k colors. The constraints are:

- No two adjacent houses may share the same color.
- The cost of painting house i with color j is given by `costs[i][j]`.

A naive approach that tries every valid combination would be exponential, but dynamic programming provides an efficient polynomial solution.

## Dynamic Programming Approach

### Naive O(n·k²) Solution

The straightforward dynamic programming formulation defines `dp[i][j]` as the minimum cost to paint houses 0 through i, where house i is painted color j.

The recurrence relation is:

```

dp[i][j] = costs[i][j] + min{ dp[i-1][c] | c ≠ j }

```

This requires scanning all k colors for each house to find the minimum of the previous row (excluding color j), resulting in **O(n·k²)** time complexity. For large k, this is too slow.

### Optimized O(n·k) Solution

The key insight is that for each row i-1, we only need the **two smallest** values among all `dp[i-1][*]`:

- `min1`: the index of the smallest cost in the previous row.
- `min2`: the index of the second-smallest cost in the previous row.

When computing `dp[i][j]`, we can determine the best previous cost in O(1):

- If `j != min1`, use the cost at `min1` from the previous row.
- If `j == min1`, use the cost at `min2` from the previous row (since we cannot use the same color).

While iterating through the current row, we simultaneously track the new `min1` and `min2` for the next iteration. This optimization reduces the time complexity to **O(n·k)** with **O(1)** extra space, as the input `costs` matrix is reused to store DP values.

## Implementation in Java

The complete implementation is located in the **kdn251/interviews** repository at [`leetcode/dynamic-programming/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/PaintHouseII.java). A variant prepared for Facebook interview preparation is also available at [`company/facebook/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/PaintHouseII.java).

The core method `minCostII` implements the optimized DP approach:

```java
public int minCostII(int[][] costs) {
    if (costs == null || costs.length == 0) {
        return 0;
    }
    
    int n = costs.length;
    int k = costs[0].length;
    int min1 = -1;  // index of minimum cost in previous row
    int min2 = -1;  // index of second minimum cost in previous row
    
    for (int i = 0; i < n; i++) {
        int last1 = min1;
        int last2 = min2;
        min1 = -1;
        min2 = -1;
        
        for (int j = 0; j < k; j++) {
            // Add the minimum cost from previous row (excluding same color)
            if (j != last1) {
                costs[i][j] += (last1 < 0) ? 0 : costs[i - 1][last1];
            } else {
                costs[i][j] += (last2 < 0) ? 0 : costs[i - 1][last2];
            }
            
            // Update min1 and min2 for current row
            if (min1 < 0 || costs[i][j] < costs[i][min1]) {
                min2 = min1;
                min1 = j;
            } else if (min2 < 0 || costs[i][j] < costs[i][min2]) {
                min2 = j;
            }
        }
    }
    
    return costs[n - 1][min1];
}

```

This implementation reuses the `costs` matrix to store cumulative minimum costs, eliminating the need for a separate DP table and achieving O(1) auxiliary space complexity.

## Step-by-Step Algorithm Walkthrough

The algorithm processes each house sequentially while maintaining only the two best color choices from the previous house:

| Step | Action | Purpose |
|------|--------|---------|
| 1 | Validate input; return 0 if `costs` is empty or null. | Handle edge cases gracefully. |
| 2 | Initialize `min1` and `min2` to -1 (no previous minima). | Prepare to track smallest and second-smallest costs. |
| 3 | For each house `i`, save previous minima (`last1`, `last2`) and reset `min1`, `min2`. | Propagate optimal substructure from previous row. |
| 4 | For each color `j`: if `j != last1`, add `costs[i-1][last1]`; else add `costs[i-1][last2]`. | Ensure adjacent houses have different colors while using the minimum valid previous cost. |
| 5 | Update `min1` and `min2` based on newly computed `costs[i][j]`. | Maintain the two smallest values for next iteration. |
| 6 | After processing all houses, return `costs[n-1][min1]`. | The global minimum resides in the smallest entry of the last row. |

This approach guarantees that each house-color pair is processed exactly once, yielding linear time complexity relative to the total number of houses and colors.

## Related Problems and Files

The **kdn251/interviews** repository contains several related dynamic programming solutions that demonstrate similar optimization techniques:

- **[`leetcode/dynamic-programming/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/PaintHouseII.java)**: The primary O(n·k) solution discussed in this article.
- **[`company/facebook/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/PaintHouseII.java)**: Interview-specific variant for Facebook preparation.
- **[`leetcode/dynamic-programming/paintFence.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/paintFence.java)**: Related problem using similar two-minimum optimization for painting fences with k colors.
- **[`leetcode/dynamic-programming/houseRobber.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/houseRobber.java)**: Classic DP problem demonstrating optimal substructure in house-related scenarios.

These files illustrate how tracking limited state information (such as the two smallest values) can reduce polynomial factors in dynamic programming solutions.

## Summary

- **Problem**: Minimize painting cost for n houses with k colors where adjacent houses cannot share the same color.
- **Naive approach**: O(n·k²) time by scanning all previous colors for each state.
- **Optimal approach**: O(n·k) time and O(1) space by tracking only the two minimum costs from the previous house.
- **Implementation**: The `minCostII` method in [`leetcode/dynamic-programming/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/PaintHouseII.java) reuses the input matrix to store DP values.
- **Key insight**: When computing the current house's cost for color j, use the previous row's minimum if j differs from that minimum's color; otherwise use the second minimum.

## Frequently Asked Questions

### What is the time complexity of the optimal Paint House II solution?

The optimal solution runs in **O(n·k)** time, where n is the number of houses and k is the number of colors. This is achieved by tracking only the two minimum values from the previous row rather than scanning all k colors for each state, reducing the time complexity from the naive O(n·k²).

### Can the Paint House II algorithm be implemented without modifying the input matrix?

Yes, though the implementation in [`leetcode/dynamic-programming/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/PaintHouseII.java) reuses the `costs` matrix to achieve O(1) auxiliary space. You could create a separate DP table with the same dimensions, which would use O(n·k) space but preserve the original input. The choice depends on whether space optimization or input preservation is prioritized for your specific use case.

### How does Paint House II differ from the original Paint House problem?

The original Paint House problem restricts the palette to **three colors** (typically red, blue, and green), while Paint House II generalizes this to **k colors**. This generalization makes the naive O(n·k²) approach potentially inefficient for large k, necessitating the two-minimum optimization technique that tracks the smallest and second-smallest costs from the previous house.

### Where can I find the complete Java implementation in the kdn251/interviews repository?

The complete implementation is located at [`leetcode/dynamic-programming/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/leetcode/dynamic-programming/PaintHouseII.java) in the **kdn251/interviews** repository. A variant prepared specifically for Facebook interview preparation is also available at [`company/facebook/PaintHouseII.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/PaintHouseII.java). Both files implement the `minCostII` method using the O(n·k) dynamic programming approach with O(1) auxiliary space.