Paint House II - Practice Coding Problems

Paint House II - Problem

Paint House II is a classic dynamic programming problem where you need to minimize the cost of painting houses while following a constraint.

You're given n houses arranged in a row and k different colors. Each house can be painted with any of the k colors, but here's the catch: no two adjacent houses can have the same color.

The cost of painting each house with a specific color is given in an n × k matrix called costs, where costs[i][j] represents the cost of painting house i with color j.

Goal: Find the minimum total cost to paint all houses while satisfying the adjacency constraint.

Example: If costs = [[17,2,17],[16,16,5],[14,3,19]], you have 3 houses and 3 colors. The optimal solution might be: paint house 0 with color 1 (cost 2), house 1 with color 2 (cost 5), and house 2 with color 1 (cost 3), for a total cost of 10.

Input & Output

example_1.py — Basic Case

$ Input: costs = [[17,2,17],[16,16,5],[14,3,19]]

› Output: 10

💡 Note: Paint house 0 with color 1 (cost=2), house 1 with color 2 (cost=5), house 2 with color 1 (cost=3). Total cost = 2+5+3 = 10. This is optimal since adjacent houses have different colors and total cost is minimized.

example_2.py — Single House

$ Input: costs = [[7,6,2]]

› Output: 2

💡 Note: With only one house, we simply choose the cheapest color available, which is color 2 with cost 2. No adjacency constraints apply.

example_3.py — Two Colors Only

$ Input: costs = [[1,5],[2,3],[4,1]]

› Output: 5

💡 Note: With only 2 colors, we alternate: House 0→Color 0 (cost=1), House 1→Color 1 (cost=3), House 2→Color 0 (cost=4). Total = 1+3+1 = 5. Alternative path gives 5+2+4 = 11, so first path is optimal.

Constraints

costs.length == n
costs[i].length == k
1 ≤ n ≤ 100
2 ≤ k ≤ 20
1 ≤ costs[i][j] ≤ 20
Follow-up: Could you solve it in O(nk) time and O(1) space?

Visualization

Tap to expand

Understanding the Visualization

Analyze First House

Look at all color options for the first house and identify the cheapest and second cheapest

Move to Next House

For each color option, use the minimum cost from previous house if it's a different color, otherwise use second minimum

Track Best Options

Keep track of the minimum and second minimum costs for current house to use for next house

Continue Pattern

Repeat this process for all houses, always ensuring adjacent houses have different colors

Key Takeaway

🎯 Key Insight: We only need to track the minimum and second minimum costs from the previous step, not the entire history. This reduces space complexity to O(1) while maintaining optimal O(n×k) time complexity.

Asked in

G Google 45 a Amazon 38 f Facebook 32 ⊞ Microsoft 28

The optimal solution uses dynamic programming with a key optimization: instead of storing the entire DP table, we only track the minimum and second minimum costs from the previous house. This achieves O(n×k) time complexity and O(1) space complexity. For each house and color, we add the minimum cost from the previous house (or second minimum if it's the same color), ensuring no adjacent houses share colors while minimizing total cost.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Dynamic Programming (Constant Space)	O(n*k)	O(1)	Track only minimum and second minimum from previous row to achieve O(nk) time and O(1) space
Brute Force (Try All Combinations)	O(k^n)	O(n)	Generate all possible color combinations and pick the one with minimum cost
Dynamic Programming (Bottom-Up)	O(n*k²)	O(n*k)	Build solution from smaller subproblems using memoization

Optimized Dynamic Programming (Constant Space) — Algorithm Steps

Initialize with costs of first house, track min and second min
For each subsequent house, calculate new min and second min
For each color: add min cost from previous house (or second min if same color)
Update min and second min values for current house
Return the minimum cost from the last house

Visualization

Tap to expand

Step-by-Step Walkthrough

Process First House

Find minimum and second minimum costs, track minimum's color index

For Each Subsequent House

Calculate cost using min or second min from previous house

Smart Color Selection

Use previous min if different color, second min if same color

Update Tracking Variables

Find new min and second min for current house

Code -

solution.c — C

#include <stdio.h>
#include <limits.h>

int minCostII(int** costs, int n, int k) {
    if (n == 0) return 0;
    if (k == 1) return n == 1 ? costs[0][0] : INT_MAX;
    
    int prevMin = 0, prevSecondMin = 0, prevMinIdx = -1;
    
    for (int i = 0; i < n; i++) {
        int currMin = INT_MAX, currSecondMin = INT_MAX, currMinIdx = -1;
        
        for (int j = 0; j < k; j++) {
            int cost = costs[i][j] + ((j != prevMinIdx) ? prevMin : prevSecondMin);
            
            if (cost < currMin) {
                currSecondMin = currMin;
                currMin = cost;
                currMinIdx = j;
            } else if (cost < currSecondMin) {
                currSecondMin = cost;
            }
        }
        
        prevMin = currMin;
        prevSecondMin = currSecondMin;
        prevMinIdx = currMinIdx;
    }
    
    return prevMin;
}

int main() {
    // Example usage
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n*k)

For each of n houses, we process k colors once, with O(1) operations per color

✓ Linear Growth

Space Complexity

O(1)

Only store minimum and second minimum costs from previous house, plus current house calculations

✓ Linear Space

58.2K Views

Medium-High Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Dynamic Programming (Constant Space) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler