Facebook Pixel

1473. Paint House III

HardArrayDynamic Programming
Leetcode Link

Problem Description

You have a row of m houses that need to be painted with one of n colors (labeled from 1 to n). Some houses are already painted and should not be repainted.

A neighborhood is defined as a maximal group of continuous houses painted with the same color. For example, if houses = [1,2,2,3,3,2,1,1], there are 5 neighborhoods: [{1}, {2,2}, {3,3}, {2}, {1,1}].

You are given:

  • An array houses where houses[i] represents:
    • The color of house i (if already painted)
    • 0 if the house is not painted yet
  • An m x n matrix cost where cost[i][j] is the cost to paint house i with color j + 1
  • An integer target representing the desired number of neighborhoods

Your task is to find the minimum cost to paint all unpainted houses such that the total number of neighborhoods equals exactly target. If it's impossible to achieve exactly target neighborhoods, return -1.

The key constraints are:

  • Already painted houses cannot be repainted
  • You must create exactly target neighborhoods
  • Each unpainted house must be assigned one of the n available colors
  • The cost of painting each house with each color is given in the cost matrix
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The problem asks us to find the minimum cost to paint houses while maintaining exactly target neighborhoods. This is a classic optimization problem with constraints, which suggests dynamic programming as a potential approach.

Let's think about what information we need to track as we process each house:

  1. Which house we're currently at - we need to make decisions for each house sequentially
  2. What color the previous house was painted - this determines whether we're continuing a neighborhood or starting a new one
  3. How many neighborhoods we've formed so far - we need exactly target neighborhoods at the end

This naturally leads to a 3-dimensional DP state: f[i][j][k] representing the minimum cost to paint houses from index 0 to i, where house i is painted with color j, and we've formed exactly k neighborhoods.

The key insight is how neighborhoods are formed:

  • If we paint the current house the same color as the previous house, we're extending the current neighborhood (no new neighborhood is created)
  • If we paint the current house a different color than the previous house, we're starting a new neighborhood (neighborhood count increases by 1)

For each house, we have two scenarios:

  1. House is already painted: We can't change its color, so we only need to calculate the cost based on whether it forms a new neighborhood or not (cost is 0 since no painting is needed)
  2. House is not painted: We try all possible colors and add the painting cost, considering whether each color choice creates a new neighborhood

The transition between states depends on comparing the current house's color with the previous house's color:

  • If j == j0 (same color as previous): f[i][j][k] = f[i-1][j0][k] + cost (if needed)
  • If j != j0 (different color): f[i][j][k] = f[i-1][j0][k-1] + cost (if needed)

By building up the solution house by house, tracking all possible color and neighborhood combinations, we can find the minimum cost to achieve exactly target neighborhoods. The final answer is the minimum among all possible colors for the last house with exactly target neighborhoods.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement a 3D dynamic programming solution where f[i][j][k] represents the minimum cost to paint houses from index 0 to i, with house i painted in color j, forming exactly k neighborhoods.

Initialization:

  • Create a 3D array f with dimensions [m][n+1][target+1], initialized to infinity
  • For the first house (index 0):
    • If unpainted: f[0][j][1] = cost[0][j-1] for each color j
    • If already painted: f[0][houses[0]][1] = 0

Main DP Loop: For each house i from 1 to m-1:

  1. If house is unpainted (houses[i] == 0):

    • Try all possible colors j from 1 to n
    • For each valid neighborhood count k from 1 to min(target, i+1):
      • For each possible previous color j0:
        • If j == j0 (same color, extend neighborhood): 
          f[i][j][k] = min(f[i][j][k], f[i-1][j][k] + cost[i][j-1])
        • If j != j0 (different color, new neighborhood): 
          f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1] + cost[i][j-1])

  2. If house is already painted (houses[i] != 0):

    • Set j = houses[i] (fixed color)
    • For each valid neighborhood count k:
      • For each possible previous color j0:
        • If j == j0 (same color, extend neighborhood): 
          f[i][j][k] = min(f[i][j][k], f[i-1][j][k])
        • If j != j0 (different color, new neighborhood): 
          f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1])
    • No painting cost is added since the house is already painted

Finding the Answer:

  • After processing all houses, check f[m-1][j][target] for all colors j
  • Return the minimum value found
  • If all values are infinity, return -1 (impossible to achieve target neighborhoods)

Key Optimizations:

  • The neighborhood count k is bounded by min(target+1, i+2) since we can't have more neighborhoods than houses processed so far
  • We use 1-indexed colors to match the problem's color labeling (1 to n)
  • The cost array uses 0-indexing, so we access cost[i][j-1] for color j

The time complexity is O(m * n^2 * target) and space complexity is O(m * n * target).

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

  • houses = [0, 2, 0] (3 houses, middle one is already painted with color 2)
  • cost = [[1, 10], [10, 1], [1, 10]] (costs to paint each house with colors 1 or 2)
  • target = 2 (we want exactly 2 neighborhoods)
  • n = 2 (2 colors available)

Goal: Paint the unpainted houses (indices 0 and 2) to form exactly 2 neighborhoods with minimum cost.

DP Setup: We create f[i][j][k] where:

  • i = house index (0 to 2)
  • j = color (1 or 2)
  • k = number of neighborhoods formed (1 or 2)

Step 1: Initialize for house 0 House 0 is unpainted, so we can paint it with either color:

  • f[0][1][1] = cost[0][0] = 1 (paint house 0 with color 1, forming 1 neighborhood)
  • f[0][2][1] = cost[0][1] = 10 (paint house 0 with color 2, forming 1 neighborhood)

Step 2: Process house 1 House 1 is already painted with color 2 (no cost to add):

For k = 1 (maintaining 1 neighborhood):

  • f[1][2][1] = f[0][2][1] + 0 = 10 (previous house was also color 2, same neighborhood)

For k = 2 (forming 2 neighborhoods):

  • f[1][2][2] = f[0][1][1] + 0 = 1 (previous house was color 1, different from 2, new neighborhood)

Step 3: Process house 2 House 2 is unpainted, so we try both colors:

For color 1, k = 2:

  • From previous color 2 (different): f[2][1][2] = f[1][2][1] + cost[2][0] = 10 + 1 = 11

For color 1, k = 3:

  • From previous color 2 (different): f[2][1][3] = f[1][2][2] + cost[2][0] = 1 + 1 = 2
  • But wait! We only want target = 2 neighborhoods, so we don't consider k = 3.

For color 2, k = 1:

  • From previous color 2 (same): f[2][2][1] = f[1][2][1] + cost[2][1] = 10 + 10 = 20

For color 2, k = 2:

  • From previous color 2 (same): f[2][2][2] = f[1][2][2] + cost[2][1] = 1 + 10 = 11

Step 4: Find the answer We look at f[2][j][2] for all colors j:

  • f[2][1][2] = 11 (end with color 1, 2 neighborhoods)
  • f[2][2][2] = 11 (end with color 2, 2 neighborhoods)

The minimum cost is 11.

Verification: One optimal solution: Paint house 0 with color 1 (cost 1), house 1 is already color 2, paint house 2 with color 2 (cost 10). This gives us colors [1, 2, 2] with 2 neighborhoods: [{1}, {2,2}]. Total cost = 1 + 10 = 11.

Solution Implementation

1class Solution:
2    def minCost(
3        self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int
4    ) -> int:
5        # Initialize DP table: dp[house_idx][color][num_neighborhoods]
6        # dp[i][j][k] = minimum cost to paint houses 0..i where house i has color j 
7        # and forms exactly k neighborhoods
8        INF = float('inf')
9        dp = [[[INF] * (target + 1) for _ in range(n + 1)] for _ in range(m)]
10      
11        # Base case: handle the first house
12        if houses[0] == 0:
13            # First house is unpainted, try all possible colors
14            for color_idx, paint_cost in enumerate(cost[0], 1):
15                dp[0][color_idx][1] = paint_cost
16        else:
17            # First house is already painted, no cost needed
18            dp[0][houses[0]][1] = 0
19      
20        # Fill the DP table for remaining houses
21        for house_idx in range(1, m):
22            if houses[house_idx] == 0:
23                # Current house is unpainted, try all possible colors
24                for current_color in range(1, n + 1):
25                    # Try different numbers of neighborhoods (up to house_idx + 1)
26                    for num_neighborhoods in range(1, min(target + 1, house_idx + 2)):
27                        # Consider all possible colors of the previous house
28                        for prev_color in range(1, n + 1):
29                            if current_color == prev_color:
30                                # Same color as previous house, no new neighborhood
31                                dp[house_idx][current_color][num_neighborhoods] = min(
32                                    dp[house_idx][current_color][num_neighborhoods],
33                                    dp[house_idx - 1][prev_color][num_neighborhoods] + cost[house_idx][current_color - 1]
34                                )
35                            else:
36                                # Different color from previous house, creates new neighborhood
37                                dp[house_idx][current_color][num_neighborhoods] = min(
38                                    dp[house_idx][current_color][num_neighborhoods],
39                                    dp[house_idx - 1][prev_color][num_neighborhoods - 1] + cost[house_idx][current_color - 1]
40                                )
41            else:
42                # Current house is already painted with a specific color
43                current_color = houses[house_idx]
44                # Try different numbers of neighborhoods
45                for num_neighborhoods in range(1, min(target + 1, house_idx + 2)):
46                    # Consider all possible colors of the previous house
47                    for prev_color in range(1, n + 1):
48                        if current_color == prev_color:
49                            # Same color as previous house, no new neighborhood
50                            dp[house_idx][current_color][num_neighborhoods] = min(
51                                dp[house_idx][current_color][num_neighborhoods],
52                                dp[house_idx - 1][prev_color][num_neighborhoods]
53                            )
54                        else:
55                            # Different color from previous house, creates new neighborhood
56                            dp[house_idx][current_color][num_neighborhoods] = min(
57                                dp[house_idx][current_color][num_neighborhoods],
58                                dp[house_idx - 1][prev_color][num_neighborhoods - 1]
59                            )
60      
61        # Find the minimum cost among all possible colors for the last house
62        # with exactly target neighborhoods
63        min_cost = min(dp[-1][color][target] for color in range(1, n + 1))
64      
65        # Return -1 if impossible, otherwise return the minimum cost
66        return -1 if min_cost >= INF else min_cost
67
1class Solution {
2    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
3        // dp[i][j][k] represents the minimum cost to paint houses 0 to i
4        // where house i is painted with color j and we have k neighborhoods
5        int[][][] dp = new int[m][n + 1][target + 1];
6        final int INF = 1 << 30;
7      
8        // Initialize all values to infinity
9        for (int[][] row : dp) {
10            for (int[] col : row) {
11                Arrays.fill(col, INF);
12            }
13        }
14      
15        // Base case: initialize first house
16        if (houses[0] == 0) {
17            // If first house is not painted, try all colors
18            for (int color = 1; color <= n; ++color) {
19                dp[0][color][1] = cost[0][color - 1];
20            }
21        } else {
22            // If first house is already painted, no cost needed
23            dp[0][houses[0]][1] = 0;
24        }
25      
26        // Fill the dp table for remaining houses
27        for (int houseIdx = 1; houseIdx < m; ++houseIdx) {
28            if (houses[houseIdx] == 0) {
29                // Current house is not painted, try all possible colors
30                for (int curColor = 1; curColor <= n; ++curColor) {
31                    for (int neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
32                        // Try all possible colors for previous house
33                        for (int prevColor = 1; prevColor <= n; ++prevColor) {
34                            if (curColor == prevColor) {
35                                // Same color as previous house, neighborhoods count stays same
36                                dp[houseIdx][curColor][neighborhoods] = Math.min(
37                                    dp[houseIdx][curColor][neighborhoods], 
38                                    dp[houseIdx - 1][curColor][neighborhoods] + cost[houseIdx][curColor - 1]
39                                );
40                            } else {
41                                // Different color from previous house, neighborhoods count increases by 1
42                                dp[houseIdx][curColor][neighborhoods] = Math.min(
43                                    dp[houseIdx][curColor][neighborhoods], 
44                                    dp[houseIdx - 1][prevColor][neighborhoods - 1] + cost[houseIdx][curColor - 1]
45                                );
46                            }
47                        }
48                    }
49                }
50            } else {
51                // Current house is already painted
52                int curColor = houses[houseIdx];
53                for (int neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
54                    // Try all possible colors for previous house
55                    for (int prevColor = 1; prevColor <= n; ++prevColor) {
56                        if (curColor == prevColor) {
57                            // Same color as previous house, neighborhoods count stays same
58                            dp[houseIdx][curColor][neighborhoods] = Math.min(
59                                dp[houseIdx][curColor][neighborhoods], 
60                                dp[houseIdx - 1][curColor][neighborhoods]
61                            );
62                        } else {
63                            // Different color from previous house, neighborhoods count increases by 1
64                            dp[houseIdx][curColor][neighborhoods] = Math.min(
65                                dp[houseIdx][curColor][neighborhoods], 
66                                dp[houseIdx - 1][prevColor][neighborhoods - 1]
67                            );
68                        }
69                    }
70                }
71            }
72        }
73      
74        // Find the minimum cost among all possible colors for the last house
75        // with exactly target neighborhoods
76        int minCostResult = INF;
77        for (int color = 1; color <= n; ++color) {
78            minCostResult = Math.min(minCostResult, dp[m - 1][color][target]);
79        }
80      
81        // Return -1 if no valid solution exists, otherwise return the minimum cost
82        return minCostResult >= INF ? -1 : minCostResult;
83    }
84}
85
1class Solution {
2public:
3    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
4        // dp[i][j][k] represents the minimum cost to paint houses 0 to i
5        // where house i is painted with color j and forms k neighborhoods
6        const int INF = 0x3f3f3f3f;
7        int dp[m][n + 1][target + 1];
8        memset(dp, 0x3f, sizeof(dp));
9      
10        // Initialize first house
11        if (houses[0] == 0) {
12            // First house is not painted, try all colors
13            for (int color = 1; color <= n; ++color) {
14                dp[0][color][1] = cost[0][color - 1];
15            }
16        } else {
17            // First house is already painted
18            dp[0][houses[0]][1] = 0;
19        }
20      
21        // Process remaining houses
22        for (int i = 1; i < m; ++i) {
23            if (houses[i] == 0) {
24                // Current house is not painted, try all colors
25                for (int curColor = 1; curColor <= n; ++curColor) {
26                    // Try different number of neighborhoods (up to target and i+1)
27                    for (int neighborhoods = 1; neighborhoods <= min(target, i + 1); ++neighborhoods) {
28                        // Try all possible colors for previous house
29                        for (int prevColor = 1; prevColor <= n; ++prevColor) {
30                            if (curColor == prevColor) {
31                                // Same color as previous house, neighborhoods count stays the same
32                                dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods], 
33                                                                    dp[i - 1][prevColor][neighborhoods] + cost[i][curColor - 1]);
34                            } else {
35                                // Different color from previous house, creates a new neighborhood
36                                dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods], 
37                                                                    dp[i - 1][prevColor][neighborhoods - 1] + cost[i][curColor - 1]);
38                            }
39                        }
40                    }
41                }
42            } else {
43                // Current house is already painted
44                int curColor = houses[i];
45                // Try different number of neighborhoods (up to target and i+1)
46                for (int neighborhoods = 1; neighborhoods <= min(target, i + 1); ++neighborhoods) {
47                    // Try all possible colors for previous house
48                    for (int prevColor = 1; prevColor <= n; ++prevColor) {
49                        if (curColor == prevColor) {
50                            // Same color as previous house, neighborhoods count stays the same
51                            dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods], 
52                                                               dp[i - 1][prevColor][neighborhoods]);
53                        } else {
54                            // Different color from previous house, creates a new neighborhood
55                            dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods], 
56                                                               dp[i - 1][prevColor][neighborhoods - 1]);
57                        }
58                    }
59                }
60            }
61        }
62      
63        // Find minimum cost among all possible colors for the last house with exactly target neighborhoods
64        int minCostResult = INF;
65        for (int lastColor = 1; lastColor <= n; ++lastColor) {
66            minCostResult = min(minCostResult, dp[m - 1][lastColor][target]);
67        }
68      
69        // Return -1 if impossible to achieve target neighborhoods, otherwise return minimum cost
70        return minCostResult == INF ? -1 : minCostResult;
71    }
72};
73
1/**
2 * Finds the minimum cost to paint houses forming exactly target neighborhoods
3 * @param houses - Array where houses[i] is the color of house i (0 means unpainted)
4 * @param cost - 2D array where cost[i][j] is the cost to paint house i with color j+1
5 * @param m - Number of houses
6 * @param n - Number of available colors (1 to n)
7 * @param target - Target number of neighborhoods
8 * @returns Minimum cost to paint all houses, or -1 if impossible
9 */
10function minCost(houses: number[], cost: number[][], m: number, n: number, target: number): number {
11    // Define infinity as a large number for impossible states
12    const INFINITY = 1 << 30;
13  
14    // Initialize DP table: dp[houseIndex][color][neighborhoodCount]
15    // dp[i][j][k] represents minimum cost to paint houses 0..i where:
16    // - house i is painted with color j
17    // - there are exactly k neighborhoods formed
18    const dp: number[][][] = new Array(m)
19        .fill(0)
20        .map(() => new Array(n + 1)
21            .fill(0)
22            .map(() => new Array(target + 1).fill(INFINITY)));
23  
24    // Base case: Initialize first house
25    if (houses[0] === 0) {
26        // First house is unpainted, try all colors
27        for (let color = 1; color <= n; ++color) {
28            // Painting first house creates exactly 1 neighborhood
29            dp[0][color][1] = cost[0][color - 1];
30        }
31    } else {
32        // First house is already painted
33        dp[0][houses[0]][1] = 0;
34    }
35  
36    // Fill DP table for remaining houses
37    for (let houseIdx = 1; houseIdx < m; ++houseIdx) {
38        if (houses[houseIdx] === 0) {
39            // Current house is unpainted, try all possible colors
40            for (let currentColor = 1; currentColor <= n; ++currentColor) {
41                // Try all possible neighborhood counts (up to current house count)
42                for (let neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
43                    // Check all possible colors of previous house
44                    for (let previousColor = 1; previousColor <= n; ++previousColor) {
45                        if (previousColor === currentColor) {
46                            // Same color as previous house - no new neighborhood
47                            dp[houseIdx][currentColor][neighborhoods] = Math.min(
48                                dp[houseIdx][currentColor][neighborhoods],
49                                dp[houseIdx - 1][currentColor][neighborhoods] + cost[houseIdx][currentColor - 1]
50                            );
51                        } else {
52                            // Different color from previous house - creates new neighborhood
53                            dp[houseIdx][currentColor][neighborhoods] = Math.min(
54                                dp[houseIdx][currentColor][neighborhoods],
55                                dp[houseIdx - 1][previousColor][neighborhoods - 1] + cost[houseIdx][currentColor - 1]
56                            );
57                        }
58                    }
59                }
60            }
61        } else {
62            // Current house is already painted
63            const currentColor = houses[houseIdx];
64          
65            // Try all possible neighborhood counts
66            for (let neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
67                // Check all possible colors of previous house
68                for (let previousColor = 1; previousColor <= n; ++previousColor) {
69                    if (previousColor === currentColor) {
70                        // Same color as previous house - no new neighborhood
71                        dp[houseIdx][currentColor][neighborhoods] = Math.min(
72                            dp[houseIdx][currentColor][neighborhoods],
73                            dp[houseIdx - 1][currentColor][neighborhoods]
74                        );
75                    } else {
76                        // Different color from previous house - creates new neighborhood
77                        dp[houseIdx][currentColor][neighborhoods] = Math.min(
78                            dp[houseIdx][currentColor][neighborhoods],
79                            dp[houseIdx - 1][previousColor][neighborhoods - 1]
80                        );
81                    }
82                }
83            }
84        }
85    }
86  
87    // Find minimum cost among all possible colors for the last house
88    let minimumCost = INFINITY;
89    for (let color = 1; color <= n; ++color) {
90        minimumCost = Math.min(minimumCost, dp[m - 1][color][target]);
91    }
92  
93    // Return -1 if impossible, otherwise return the minimum cost
94    return minimumCost >= INFINITY ? -1 : minimumCost;
95}
96

Time and Space Complexity

Time Complexity: O(m × n² × target)

The analysis breaks down as follows:

  • The outer loop iterates through m houses (from index 1 to m-1)
  • For each house, we iterate through up to n possible colors for the current house (variable j)
  • For each color, we iterate through up to target possible neighborhood counts (variable k)
  • For each neighborhood count, we iterate through n possible colors of the previous house (variable j0)
  • The initialization phase for the first house takes O(n) time

Therefore, the overall time complexity is O(m × n × target × n) = O(m × n² × target)

Space Complexity: O(m × n × target)

The space complexity is determined by the 3D DP array f:

  • First dimension: m houses
  • Second dimension: n + 1 colors (indexed from 0 to n)
  • Third dimension: target + 1 neighborhood counts (indexed from 0 to target)

The array f has dimensions [m][n+1][target+1], resulting in a space complexity of O(m × n × target)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Color Indexing Between Houses and Cost Arrays

One of the most common mistakes is confusion between the color indexing systems:

  • The houses array uses 1-based indexing for colors (1 to n), with 0 indicating unpainted
  • The cost matrix uses 0-based indexing where cost[i][j] represents the cost to paint house i with color j+1

Pitfall Example:

# WRONG: Using color directly as index in cost array
if houses[house_idx] == 0:
    for current_color in range(1, n + 1):
        # This will cause IndexError or use wrong cost
        painting_cost = cost[house_idx][current_color]  # ❌ Wrong!

Solution:

# CORRECT: Subtract 1 when accessing cost array
if houses[house_idx] == 0:
    for current_color in range(1, n + 1):
        painting_cost = cost[house_idx][current_color - 1]  # ✓ Correct!

2. Forgetting to Skip Painting Cost for Already Painted Houses

When a house is already painted, adding its painting cost is incorrect since we cannot repaint it.

Pitfall Example:

# WRONG: Adding cost even for already painted houses
if houses[house_idx] != 0:
    current_color = houses[house_idx]
    # Adding cost here is wrong!
    dp[house_idx][current_color][num_neighborhoods] = min(
        dp[house_idx][current_color][num_neighborhoods],
        dp[house_idx - 1][prev_color][num_neighborhoods] + cost[house_idx][current_color - 1]  # ❌
    )

Solution:

# CORRECT: No cost added for already painted houses
if houses[house_idx] != 0:
    current_color = houses[house_idx]
    dp[house_idx][current_color][num_neighborhoods] = min(
        dp[house_idx][current_color][num_neighborhoods],
        dp[house_idx - 1][prev_color][num_neighborhoods]  # ✓ No cost added
    )

3. Incorrect Neighborhood Count Bounds

The maximum number of neighborhoods at house i cannot exceed i+1 (one neighborhood per house). Using target+1 as the upper bound for all houses wastes computation and can lead to logic errors.

Pitfall Example:

# WRONG: Always iterating up to target+1 neighborhoods
for num_neighborhoods in range(1, target + 1):  # ❌ Inefficient and potentially wrong
    # This allows invalid states where neighborhoods > houses

Solution:

# CORRECT: Limit neighborhoods to min(target+1, house_idx+2)
for num_neighborhoods in range(1, min(target + 1, house_idx + 2)):  # ✓
    # This ensures we never have more neighborhoods than houses

4. Not Handling the Base Case Correctly

The first house requires special handling since it always forms exactly 1 neighborhood, and there's no previous house to consider.

Pitfall Example:

# WRONG: Trying to access previous house for index 0
for house_idx in range(m):  # Starting from 0
    for prev_color in range(1, n + 1):
        # This will fail when house_idx = 0
        dp[house_idx][current_color][k] = dp[house_idx - 1][prev_color][k]  # ❌ Index -1!

Solution:

# CORRECT: Handle first house separately
if houses[0] == 0:
    for color_idx, paint_cost in enumerate(cost[0], 1):
        dp[0][color_idx][1] = paint_cost
else:
    dp[0][houses[0]][1] = 0

# Then process remaining houses starting from index 1
for house_idx in range(1, m):  # ✓ Start from 1
    # ... rest of the logic
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More