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. You have a grid where two players start at the top-left corner and move to the bottom-right corner simultaneously, collecting cherries on their paths. Both players can only move right or down, and some cells contain thorns that block passage. The goal is to maximize the total cherries collected by both players without double-counting cherries if they land on the same cell. Which algorithmic approach guarantees finding the optimal solution for this problem?

easy

A. Greedy algorithm that always picks the next cell with the most cherries for each player independently.

B. Divide and conquer by splitting the grid into two halves and solving each half independently.

C. Dynamic programming that tracks both players' positions simultaneously and uses a 3D state to avoid double counting and invalid paths.

D. Simple BFS traversal from start to end for each player separately, then summing their maximum cherries.

Solution

1. Step 1: Understand the problem constraints

   Two players move simultaneously on the grid, collecting cherries without double counting and avoiding thorns. Both must take the same number of steps at any point.

2. Step 2: Identify the suitable algorithmic pattern

   Dynamic programming with a 3D state (step count and both players' row positions) tracks both players' positions simultaneously, ensuring valid states and avoiding double counting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP with simultaneous states handles constraints correctly [OK]

Hint: Two simultaneous paths require joint DP state [OK]

Common Mistakes:

• Assuming independent paths and summing results
• Using greedy to pick local max cherries
• Splitting grid and solving halves independently

2. The following code attempts to implement the space-optimized DP solution for Maximal Square. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1)
    max_side = 0
    prev = 0
    for i in range(rows):
        for j in range(1, cols + 1):
            temp = dp[j]
            if matrix[i][j-1] == '1':
                dp[j] = 1 + min(dp[j], dp[j-1], prev)  # Bug here
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return max_side * max_side

medium

A. Line with 'dp[j] = 1 + min(dp[j], dp[j-1], dp[j-1])'

B. Line with 'temp = dp[j]'

C. Line with 'prev = temp'

D. Line with 'max_side = max(max_side, dp[j])'

Solution

1. Step 1: Identify the DP recurrence

   The recurrence requires min(dp[j], dp[j-1], prev), but code uses dp[j-1] twice, missing 'prev'.

2. Step 2: Understand impact

   Using dp[j-1] twice ignores the diagonal value 'prev', causing incorrect dp values and max square size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses three distinct values [OK]

Hint: Check if all three DP states are used in min() [OK]

Common Mistakes:

• Forgetting to use 'prev' in min()
• Overwriting dp before using dependencies
• Incorrect dp initialization

3. 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

4. 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

5. Suppose the problem is modified so that the matrix can contain '1's and '0's, but you want to find the largest square containing only '1's where you are allowed to flip at most one '0' inside the square to '1'. Which of the following approaches correctly adapts the DP solution to handle this variant efficiently?

hard

A. Maintain two DP arrays: one for squares with zero flips and one for squares with one flip allowed, updating both simultaneously

B. Use the original DP but treat all '0's as '1's to allow flipping implicitly

C. Run the original DP multiple times, each time flipping a different '0' to '1' and taking the max result

D. Use a greedy approach to find the largest square ignoring zeros, then check if flipping one zero inside is possible

Solution

1. Step 1: Understand the variant

   Allowing one flip means tracking squares formed with zero or one zero flipped inside.

2. Step 2: Adapt DP states

   Maintain two DP states per cell: max square size without flips and with one flip used, updating both based on neighbors.

3. Step 3: Reject naive approaches

   Original DP ignores flips; multiple runs are inefficient; greedy ignores DP dependencies.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two DP arrays track flip states efficiently [OK]

Hint: Track DP states with and without flips [OK]

Common Mistakes:

• Ignoring flip state in DP
• Trying multiple brute force runs
• Using greedy without DP