Paint House (K Colors)

📋

Problem

Imagine you are a contractor tasked with painting a row of houses, each with multiple color options, but you must ensure no two adjacent houses share the same color to keep the neighborhood visually appealing.

Given a row of n houses and k colors, each house can be painted with one of the k colors at a certain cost. No two adjacent houses can have the same color. Find the minimum total cost to paint all houses.

1 ≤ n ≤ 10^51 ≤ k ≤ 100costs[i][j] is a non-negative integer representing the cost of painting house i with color j

Edge cases: n = 1, k = 1 → output is cost of single house single colorAll costs are zero → output should be zerok = 1 and n > 1 → no valid painting possible, output should handle gracefully

</>

IDE

def minCost(costs: list[list[int]]) -> int:public int minCost(int[][] costs)int minCost(vector<vector<int>>& costs)function minCost(costs)

def minCost(costs):
    # Write your solution here
    pass

class Solution {
    public int minCost(int[][] costs) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minCost(vector<vector<int>>& costs) {
    // Write your solution here
    return 0;
}

function minCost(costs) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrect minimal cost ignoring adjacency constraintsFailed to exclude same color for adjacent houses in DP transitions.✅ In DP, update dp[i][j] only using dp[i-1][x] where x != j.

Wrong: Error or wrong output on empty inputNo check for empty costs array causing runtime error or wrong return.✅ Add guard clause: if not costs: return 0.

Wrong: Wrong cost when k=1 and n>1No valid painting possible but code returns a cost anyway.✅ Add check: if k==1 and n>1 return -1 to indicate no solution.

Wrong: Greedy minimal color per house leads to suboptimal costIgnoring adjacency constraints and DP state transitions.✅ Implement DP tracking minimal and second minimal costs per house excluding previous color.

Wrong: TLE on large inputsNaive O(n*k*k) DP without optimization.✅ Optimize DP by tracking minimal and second minimal costs to achieve O(n*k).

✓

Test Cases

Handle base cases like empty input and single house carefully.

Beware of greedy traps and indexing errors in DP.

Optimize your DP to handle large inputs efficiently.

t1_01basic

Input{"costs":[[1,5,3],[2,9,4],[15,7,6]]}

Expected11

⏱ Performance - must finish in 2000ms

Optimal painting: house 0 color 0 (1), house 1 color 2 (4), house 2 color 1 (7) total cost 8.

💡 Consider dynamic programming to track minimal costs per house and color.

💡 Use DP state dp[i][j] = min cost to paint house i with color j, avoiding same color as previous house.

💡 Update dp[i][j] by adding costs[i][j] to the minimal dp[i-1][x] for x != j.

Why it failed: Incorrect minimal cost output; likely failed to exclude same color for adjacent houses or miscalculated DP transitions. Fix by ensuring dp[i][j] only considers dp[i-1][x] where x != j.

✓ Correct minimal cost computed with proper DP state transitions excluding adjacent same colors.

t1_02basic

Input{"costs":[[7,3,8,6,1,2],[5,6,7,2,4,3],[10,1,4,9,7,6]]}

Expected4

⏱ Performance - must finish in 2000ms

Optimal painting: house 0 color 4 (1), house 1 color 3 (2), house 2 color 1 (1) total cost 4.

💡 Track minimal and second minimal costs per previous house to optimize transitions.

💡 For each house, pick color with minimal cost excluding previous house's color.

💡 Use DP to accumulate minimal costs while avoiding adjacent same colors.

Why it failed: Output incorrect due to not properly excluding previous house's color or not choosing minimal costs correctly. Fix by tracking minimal and second minimal costs per row and excluding previous color.

✓ DP correctly computes minimal cost avoiding adjacent same colors.

t2_01edge

Input{"costs":[]}

Expected0

⏱ Performance - must finish in 2000ms

No houses to paint, minimal cost is 0.

💡 Check for empty input and handle base case.

💡 If no houses, return 0 immediately.

💡 Add a guard clause for empty costs array.

Why it failed: Fails on empty input by not returning 0 or causing error. Fix by adding check: if not costs: return 0.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"costs":[[10]]}

Expected10

⏱ Performance - must finish in 2000ms

Single house with single color, cost is that color's cost.

💡 For single house, minimal cost is minimal color cost.

💡 No adjacency constraints apply with one house.

💡 Return minimal cost among available colors for single house.

Why it failed: Fails single element by overcomplicating or returning wrong cost. Fix by returning min(costs[0]) when n=1.

✓ Correctly returns cost for single house single color.

t2_03edge

Input{"costs":[[5],[7],[3]]}

Expected-1

⏱ Performance - must finish in 2000ms

Only one color but multiple houses, no valid painting possible, return -1.

💡 If k=1 and n>1, no valid painting since adjacent houses must differ in color.

💡 Detect this scenario and return a sentinel value like -1.

💡 Add a check: if k=1 and n>1 return -1 to indicate no solution.

Why it failed: Fails to detect no valid painting when k=1 and n>1, returns incorrect cost. Fix by adding condition: if k==1 and n>1 return -1.

✓ Correctly returns -1 when no valid painting possible.

t3_01corner

Input{"costs":[[1,100,100],[100,1,100],[1,100,1]]}

Expected3

⏱ Performance - must finish in 2000ms

Greedy approach fails; minimal cost is 3 by painting colors 0,1,0.

💡 Greedy picking minimal cost color per house may fail due to adjacency.

💡 Use DP to consider previous house colors and avoid adjacent repeats.

💡 Track minimal and second minimal costs to optimize DP transitions.

Why it failed: Greedy approach fails by choosing minimal cost color per house ignoring adjacency. Fix by implementing DP that excludes previous house's color.

✓ DP correctly handles adjacency constraints and finds minimal cost.

t3_02corner

Input{"costs":[[1,2],[2,1],[1,2],[2,1]]}

Expected4

⏱ Performance - must finish in 2000ms

Confusing 0/1 vs unbounded: each house painted once, no repeats adjacent; minimal cost 4.

💡 Each house must be painted exactly one color, no repeats adjacent.

💡 Avoid treating problem as unbounded knapsack or multiple painting per house.

💡 DP state must represent one color per house with adjacency constraints.

Why it failed: Mistakes treating problem as unbounded or multiple painting per house, leading to wrong cost. Fix by enforcing one color per house and adjacency constraints in DP.

✓ Correctly models 0/1 painting per house with adjacency constraints.

t3_03corner

Input{"costs":[[1,2,3],[3,2,1],[1,2,3],[3,2,1]]}

Expected4

⏱ Performance - must finish in 2000ms

Off-by-one error in indexing colors or houses leads to wrong cost; minimal cost is 6.

💡 Check indexing carefully when accessing costs and DP arrays.

💡 Ensure loops cover all houses and colors correctly.

💡 Verify DP transitions use correct indices for previous house and colors.

Why it failed: Off-by-one indexing error causes incorrect DP updates and wrong cost. Fix by correcting loop bounds and indices in DP.

✓ Correct indexing yields correct minimal cost.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100000 and k=100; O(n*k*k) brute force will TLE; efficient O(n*k) or O(n*k*k) with optimization required.

💡 Naive O(n*k*k) DP may be too slow for n=100000.

💡 Optimize by tracking minimal and second minimal costs per row to reduce complexity to O(n*k).

💡 Use space optimization to handle large input efficiently.

Why it failed: TLE due to O(n*k*k) brute force DP without optimization. Fix by implementing optimized DP tracking minimal and second minimal costs.

✓ Efficient DP completes within time limit.

Practice

1. The following code attempts to solve the Burst Balloons problem using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def maxCoins(nums):
    n = len(nums)
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    nums = nums + [1, 1]
    for length in range(2, n + 2):
        for i in range(0, n + 2 - length):
            j = i + length
            for k in range(i + 1, j):
                coins = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
    return dp[0][n + 1]

medium

A. Line 4: Adding virtual balloons at the end instead of both ends

B. Line 3: Initializing dp with size (n+2) x (n+2)

C. Line 7: Looping length from 2 to n+2

D. Line 10: Calculating coins using dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]

Solution

1. Step 1: Check virtual balloon addition

   The code adds [1,1] only at the end of nums, but the algorithm requires adding 1 at both the start and end to handle boundaries correctly.

2. Step 2: Consequences of missing virtual balloon at start

   Without the leading 1, dp indices and coin calculations become incorrect, causing index errors or wrong coin counts at boundaries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Virtual balloons must be added at both ends [OK]

Hint: Always add virtual balloons at both ends to avoid boundary errors [OK]

Common Mistakes:

• Adding virtual balloons only at one end
• Incorrect dp table size
• Wrong loop boundaries

2. What is the time complexity of the bottom-up DP solution for the Cherry Pickup problem on an n x n grid, where dp is a 3D array indexed by step and two row positions of the players?

medium

A. O(4^n) due to exploring all possible paths for two players

B. O(n^3) because there are O(n) steps and O(n^2) states for the two players' rows, each computed in constant time

C. O(n^4) since for each dp state, four previous states are checked

D. O(n^2) as the dp only tracks positions of two players without step dimension

Solution

1. Step 1: Identify number of states

   There are 2n-1 steps, and for each step, possible row positions for player 1 and player 2 are each O(n), so total states are O(n^3).

2. Step 2: Analyze transitions per state

   Each dp state checks up to 4 previous states in O(1) time, so total time is O(n^3).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3D dp with O(n^3) states and constant transitions [OK]

Hint: Count states x transitions carefully [OK]

Common Mistakes:

• Confusing number of states with number of transitions
• Assuming exponential time due to recursion
• Ignoring that step dimension limits valid states

3. What is the time complexity of the bottom-up DP solution for the Triangle minimum path sum problem with n rows, and why?

medium

A. O(n^2) because each element in the triangle is processed once

B. O(2^n) because of the exponential number of paths

C. O(n) because each row is processed once

D. O(n^3) because of nested loops over rows and columns

Solution

1. Step 1: Count total elements in triangle

   Triangle has 1 + 2 + ... + n = n(n+1)/2 elements, which is O(n^2).

2. Step 2: Analyze loops

   Outer loop runs n times, inner loop runs up to n times per iteration, total O(n^2) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each element processed once in nested loops [OK]

Hint: Sum of rows is O(n^2), so time is O(n^2) [OK]

Common Mistakes:

• Confusing number of rows with total elements
• Assuming exponential complexity due to recursion
• Overestimating complexity due to nested loops

4. What is the time complexity of the optimal interval DP solution for Zuma Game (Min Moves to Clear) with board length n and hand size m, considering the state space and transitions?

medium

A. O(n^4 * m^5)

B. O(n^2 * m^3)

C. O(n^3 * m^4)

D. O(5^(n+m))

Solution

1. Step 1: Identify DP state dimensions

   The DP state depends on intervals of the board (O(n^2)) and hand counts (up to 5 colors, each up to m), leading to O(n^3 * m^4) states due to interval splits and hand count combinations.

2. Step 2: Analyze transitions and recursion

   Each state considers splits and insertions, adding an extra factor of n and m, resulting in O(n^3 * m^4) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Complexity matches known analysis for interval DP with hand states [OK]

Hint: Interval splits and hand states multiply complexity [OK]

Common Mistakes:

• Confusing n^2 intervals with n^3 due to splits
• Ignoring hand state dimension leading to underestimation
• Mistaking brute force complexity for DP complexity

5. Suppose the problem is modified so that you can take unlimited flights (reuse edges) but still want the cheapest price within K stops. Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use Bellman-Ford algorithm with K+1 iterations allowing edge reuse in each iteration

B. Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints

C. Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes

D. Use the same bottom-up DP but increase iterations to K+1 without changes

Solution

1. Step 1: Understand the unlimited reuse variant

   Unlimited reuse means cycles are allowed, so shortest path with stop constraints resembles Bellman-Ford relaxation over K+1 iterations.

2. Step 2: Identify correct algorithm

   Bellman-Ford naturally handles edge reuse and negative cycles (if any), iterating K+1 times to relax edges, matching problem constraints.

3. Step 3: Why other options fail

   Use the same bottom-up DP but increase iterations to K+1 without changes ignores edge reuse effect; Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints ignores stop constraints; Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes suggests repeated relaxation within iteration, which is inefficient and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bellman-Ford with K+1 iterations handles unlimited reuse correctly [OK]

Hint: Bellman-Ford handles edge reuse with K+1 relaxations [OK]

Common Mistakes:

• Using Dijkstra ignoring stops
• Not increasing iterations
• Trying repeated relaxations inside iteration