How to Solve the Paint House II Problem Using Dynamic Programming

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. A variant prepared for Facebook interview preparation is also available at company/facebook/PaintHouseII.java.

The core method minCostII implements the optimized DP approach:

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: The primary O(n·k) solution discussed in this article.
• company/facebook/PaintHouseII.java: Interview-specific variant for Facebook preparation.
• leetcode/dynamic-programming/paintFence.java: Related problem using similar two-minimum optimization for painting fences with k colors.
• 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 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 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 in the kdn251/interviews repository. A variant prepared specifically for Facebook interview preparation is also available at company/facebook/PaintHouseII.java. Both files implement the minCostII method using the O(n·k) dynamic programming approach with O(1) auxiliary space.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}