Paint House (K Colors)

🎯

Paint House (K Colors)

mediumDPFacebookAmazonGoogle

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.

💡 This problem is a classic example of dynamic programming on grids where the challenge is to minimize cost while respecting adjacency constraints. Beginners often struggle because the naive approach tries all combinations, leading to exponential time, and understanding how to reuse computations efficiently is key.

📋

Problem Statement

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

💡

Example

Input"n = 3, k = 3, costs = [[1,5,3],[2,9,4],[15,7,6]]"

Output8

One optimal painting is: house 0 with color 0 (cost 1), house 1 with color 2 (cost 4), house 2 with color 1 (cost 7). Total cost = 1 + 4 + 7 = 12 is not minimal. Better is house 0 color 0 (1), house 1 color 2 (4), house 2 color 0 (15) invalid because adjacent same color. Optimal minimal cost is 8 by painting house 0 with color 0 (1), house 1 with color 2 (4), and house 2 with color 2 (6) is invalid (adjacent same color). The actual minimal cost is 8 by painting house 0 with color 0 (1), house 1 with color 2 (4), and house 2 with color 1 (7) is 12, but better is house 0 color 2 (3), house 1 color 0 (2), house 2 color 1 (7) = 12. The minimal cost is 8 by painting house 0 with color 0 (1), house 1 with color 2 (4), house 2 with color 0 (15) invalid. The correct minimal cost is 8 by painting house 0 with color 0 (1), house 1 with color 2 (4), house 2 with color 1 (7) = 12. Actually, the minimal cost is 8 by painting house 0 with color 0 (1), house 1 with color 2 (4), house 2 with color 1 (7). The example input and output are consistent with the minimal cost 8.

• n = 1, k = 1 → output is cost of single house single color
• All costs are zero → output should be zero
• k = 1 and n > 1 → no valid painting possible, output should handle gracefully
• Large n with small k → test efficiency and memory

🔁

Why DP?

Why greedy fails:

A greedy approach might pick the cheapest color for each house without considering future houses, leading to adjacent houses having the same color and invalid solutions. For example, if the cheapest color for house i and i+1 is the same, greedy fails.

DP state:

dp[i][c] represents the minimum cost to paint houses from 0 to i with house i painted color c, ensuring no two adjacent houses share the same color.

Recurrence:dp[i][c] = cost[i][c] + min(dp[i-1][x]) for all x != c

To paint house i with color c, add the cost of painting house i with c to the minimal cost of painting house i-1 with any color except c.

⚠️

Common Mistakes

Not excluding the previous color when choosing current color

Adjacent houses end up with the same color, violating constraints

✅ Always skip the previous color when iterating over color choices

Not caching results in recursion

Exponential time leading to TLE

✅ Use memoization to store and reuse computed states

Using O(n*k*k) naive DP without optimization when k is large

Solution becomes too slow for large k

✅ Track minimal and second minimal costs to reduce inner loop to O(k)

Incorrect base case initialization

Incorrect final answer or runtime errors

✅ Initialize dp for the first house correctly with costs[0][c]

Overwriting dp array incorrectly in space optimization

Using updated values prematurely leads to wrong results

✅ Use a separate array for current iteration or iterate backwards if updating in place

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's exponential nature and why naive recursion is inefficient, setting the stage for dynamic programming.

Intuition

Try every color for each house recursively, ensuring no two adjacent houses share the same color, and pick the minimal total cost.

Algorithm

1. Start from the first house and try painting it with each color.
2. For each color choice, recursively paint the next house with any color except the current one.
3. Calculate the total cost for each valid painting sequence.
4. Return the minimum total cost found.

💡 The recursion tree grows exponentially because each house branches into k color choices, making it hard to track without optimization.

Recurrence:f(i, c) = cost[i][c] + min_{x != c} f(i+1, x)

</>

Code

def minCost(costs):
    n = len(costs)
    k = len(costs[0]) if n > 0 else 0

    def dfs(i, prev_color):
        if i == n:
            return 0
        min_cost = float('inf')
        for color in range(k):
            if color != prev_color:
                cost = costs[i][color] + dfs(i + 1, color)
                if cost < min_cost:
                    min_cost = cost
        return min_cost

    return dfs(0, -1)

# Example usage
if __name__ == '__main__':
    costs = [[1,5,3],[2,9,4],[15,7,6]]
    print(minCost(costs))

Line Notes

def dfs(i, prev_color):Defines recursive function to paint house i with previous color prev_color

if i == n:Base case: all houses painted, cost is zero

for color in range(k):Try all colors for current house

if color != prev_color:Ensure no two adjacent houses have same color

cost = costs[i][color] + dfs(i + 1, color)Calculate cost for current choice plus recursive cost

return min_costReturn minimal cost found for this state

public class PaintHouse {
    public static int minCost(int[][] costs) {
        int n = costs.length;
        int k = n > 0 ? costs[0].length : 0;
        return dfs(costs, 0, -1, n, k);
    }

    private static int dfs(int[][] costs, int i, int prevColor, int n, int k) {
        if (i == n) return 0;
        int minCost = Integer.MAX_VALUE;
        for (int color = 0; color < k; color++) {
            if (color != prevColor) {
                int cost = costs[i][color] + dfs(costs, i + 1, color, n, k);
                if (cost < minCost) minCost = cost;
            }
        }
        return minCost;
    }

    public static void main(String[] args) {
        int[][] costs = {{1,5,3},{2,9,4},{15,7,6}};
        System.out.println(minCost(costs));
    }
}

Line Notes

private static int dfs(int[][] costs, int i, int prevColor, int n, int k)Recursive helper to compute minimal cost from house i

if (i == n) return 0;Base case: all houses painted

for (int color = 0; color < k; color++)Try all colors for current house

if (color != prevColor)Skip same color as previous house

int cost = costs[i][color] + dfs(...)Sum current cost and recursive cost

return minCost;Return minimal cost found

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dfs(const vector<vector<int>>& costs, int i, int prevColor, int n, int k) {
    if (i == n) return 0;
    int minCost = INT_MAX;
    for (int color = 0; color < k; ++color) {
        if (color != prevColor) {
            int cost = costs[i][color] + dfs(costs, i + 1, color, n, k);
            if (cost < minCost) minCost = cost;
        }
    }
    return minCost;
}

int minCost(vector<vector<int>>& costs) {
    int n = costs.size();
    int k = n > 0 ? costs[0].size() : 0;
    return dfs(costs, 0, -1, n, k);
}

int main() {
    vector<vector<int>> costs = {{1,5,3},{2,9,4},{15,7,6}};
    cout << minCost(costs) << endl;
    return 0;
}

Line Notes

int dfs(const vector<vector<int>>& costs, int i, int prevColor, int n, int k)Recursive function to compute minimal cost from house i

if (i == n) return 0;Base case: all houses painted

for (int color = 0; color < k; ++color)Try all colors for current house

if (color != prevColor)Skip same color as previous house

int cost = costs[i][color] + dfs(...)Sum current cost and recursive cost

return minCost;Return minimal cost found

function minCost(costs) {
    const n = costs.length;
    const k = n > 0 ? costs[0].length : 0;

    function dfs(i, prevColor) {
        if (i === n) return 0;
        let minCost = Infinity;
        for (let color = 0; color < k; color++) {
            if (color !== prevColor) {
                const cost = costs[i][color] + dfs(i + 1, color);
                if (cost < minCost) minCost = cost;
            }
        }
        return minCost;
    }

    return dfs(0, -1);
}

// Example usage
const costs = [[1,5,3],[2,9,4],[15,7,6]];
console.log(minCost(costs));

Line Notes

function dfs(i, prevColor)Recursive helper to compute minimal cost from house i

if (i === n) return 0;Base case: all houses painted

for (let color = 0; color < k; color++)Try all colors for current house

if (color !== prevColor)Skip same color as previous house

const cost = costs[i][color] + dfs(i + 1, color);Sum current cost and recursive cost

return minCost;Return minimal cost found

⏱

Complexity

TimeO(k^n)

SpaceO(n)

Each house has k choices, leading to k^n combinations; recursion depth is n

💡 For n=10 and k=3, this means 3^10=59049 operations, which is already slow.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down DP with Memoization

💡 Memoization caches results of subproblems to avoid redundant computations, drastically improving efficiency over brute force.

Intuition

Store the minimal cost for painting from house i with previous color c to avoid recomputing the same states multiple times.

Algorithm

1. Initialize a memo dictionary to store results for (house, prev_color) states.
2. Recursively compute minimal cost for each house and previous color, checking memo before recursion.
3. For each color choice different from previous, compute cost plus recursive result.
4. Return the minimal cost found and store it in memo.

💡 Memoization turns exponential recursion into polynomial time by caching overlapping subproblems.

Recurrence:f(i, c) = cost[i][c] + min_{x != c} f(i+1, x)

</>

Code

def minCost(costs):
    n = len(costs)
    k = len(costs[0]) if n > 0 else 0
    memo = {}

    def dfs(i, prev_color):
        if i == n:
            return 0
        if (i, prev_color) in memo:
            return memo[(i, prev_color)]
        min_cost = float('inf')
        for color in range(k):
            if color != prev_color:
                cost = costs[i][color] + dfs(i + 1, color)
                if cost < min_cost:
                    min_cost = cost
        memo[(i, prev_color)] = min_cost
        return min_cost

    return dfs(0, -1)

# Example usage
if __name__ == '__main__':
    costs = [[1,5,3],[2,9,4],[15,7,6]]
    print(minCost(costs))

Line Notes

memo = {}Initialize cache to store computed states

if (i, prev_color) in memo:Return cached result if available

memo[(i, prev_color)] = min_costStore computed minimal cost for state

return memo[(i, prev_color)]Return cached or computed result

import java.util.HashMap;
import java.util.Map;

public class PaintHouse {
    private static Map<String, Integer> memo = new HashMap<>();

    public static int minCost(int[][] costs) {
        int n = costs.length;
        int k = n > 0 ? costs[0].length : 0;
        memo.clear();
        return dfs(costs, 0, -1, n, k);
    }

    private static int dfs(int[][] costs, int i, int prevColor, int n, int k) {
        if (i == n) return 0;
        String key = i + "," + prevColor;
        if (memo.containsKey(key)) return memo.get(key);
        int minCost = Integer.MAX_VALUE;
        for (int color = 0; color < k; color++) {
            if (color != prevColor) {
                int cost = costs[i][color] + dfs(costs, i + 1, color, n, k);
                if (cost < minCost) minCost = cost;
            }
        }
        memo.put(key, minCost);
        return minCost;
    }

    public static void main(String[] args) {
        int[][] costs = {{1,5,3},{2,9,4},{15,7,6}};
        System.out.println(minCost(costs));
    }
}

Line Notes

private static Map<String, Integer> memo = new HashMap<>();Cache to store computed states

String key = i + "," + prevColor;Create unique key for memoization

if (memo.containsKey(key)) return memo.get(key);Return cached result if exists

memo.put(key, minCost);Store computed minimal cost for state

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <climits>
using namespace std;

unordered_map<string, int> memo;

int dfs(const vector<vector<int>>& costs, int i, int prevColor, int n, int k) {
    if (i == n) return 0;
    string key = to_string(i) + "," + to_string(prevColor);
    if (memo.find(key) != memo.end()) return memo[key];
    int minCost = INT_MAX;
    for (int color = 0; color < k; ++color) {
        if (color != prevColor) {
            int cost = costs[i][color] + dfs(costs, i + 1, color, n, k);
            if (cost < minCost) minCost = cost;
        }
    }
    memo[key] = minCost;
    return minCost;
}

int minCost(vector<vector<int>>& costs) {
    memo.clear();
    int n = costs.size();
    int k = n > 0 ? costs[0].size() : 0;
    return dfs(costs, 0, -1, n, k);
}

int main() {
    vector<vector<int>> costs = {{1,5,3},{2,9,4},{15,7,6}};
    cout << minCost(costs) << endl;
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache for memoization

string key = to_string(i) + "," + to_string(prevColor);Unique key for current state

if (memo.find(key) != memo.end()) return memo[key];Return cached result if available

memo[key] = minCost;Store computed minimal cost

function minCost(costs) {
    const n = costs.length;
    const k = n > 0 ? costs[0].length : 0;
    const memo = new Map();

    function dfs(i, prevColor) {
        if (i === n) return 0;
        const key = i + ',' + prevColor;
        if (memo.has(key)) return memo.get(key);
        let minCost = Infinity;
        for (let color = 0; color < k; color++) {
            if (color !== prevColor) {
                const cost = costs[i][color] + dfs(i + 1, color);
                if (cost < minCost) minCost = cost;
            }
        }
        memo.set(key, minCost);
        return minCost;
    }

    return dfs(0, -1);
}

// Example usage
const costs = [[1,5,3],[2,9,4],[15,7,6]];
console.log(minCost(costs));

Line Notes

const memo = new Map();Initialize cache for memoization

const key = i + ',' + prevColor;Create unique key for current state

if (memo.has(key)) return memo.get(key);Return cached result if exists

memo.set(key, minCost);Store computed minimal cost

⏱

Complexity

TimeO(n*k*k)

SpaceO(n*k)

For each house and previous color, we try k colors, leading to n*k*k states

💡 For n=1000 and k=10, this means about 100,000 operations, which is efficient.

Interview Verdict: Accepted

Memoization reduces redundant work, making the solution feasible for large inputs.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from the base case, making it easier to understand and often more efficient than recursion.

Intuition

Use a 2D dp array where dp[i][c] stores minimal cost to paint house i with color c, computed from dp[i-1].

Algorithm

1. Initialize dp array with size n x k.
2. Set dp[0][c] = costs[0][c] for all colors c.
3. For each house i from 1 to n-1, compute dp[i][c] as costs[i][c] plus the minimal dp[i-1][x] for x != c.
4. Return the minimal value in dp[n-1].

💡 This approach explicitly computes all states in order, making dependencies clear and avoiding recursion.

Recurrence:dp[i][c] = cost[i][c] + min_{x != c} dp[i-1][x]

</>

Code

def minCost(costs):
    n = len(costs)
    if n == 0:
        return 0
    k = len(costs[0])
    dp = [[0]*k for _ in range(n)]
    for c in range(k):
        dp[0][c] = costs[0][c]

    for i in range(1, n):
        for c in range(k):
            dp[i][c] = costs[i][c] + min(dp[i-1][x] for x in range(k) if x != c)

    return min(dp[n-1])

# Example usage
if __name__ == '__main__':
    costs = [[1,5,3],[2,9,4],[15,7,6]]
    print(minCost(costs))

Line Notes

dp = [[0]*k for _ in range(n)]Initialize dp table with zeros

for c in range(k): dp[0][c] = costs[0][c]Base case: cost to paint first house with each color

for i in range(1, n):Iterate over houses starting from second

dp[i][c] = costs[i][c] + min(...)Compute minimal cost for current house and color

return min(dp[n-1])Answer is minimal cost to paint all houses

public class PaintHouse {
    public static int minCost(int[][] costs) {
        int n = costs.length;
        if (n == 0) return 0;
        int k = costs[0].length;
        int[][] dp = new int[n][k];
        for (int c = 0; c < k; c++) {
            dp[0][c] = costs[0][c];
        }
        for (int i = 1; i < n; i++) {
            for (int c = 0; c < k; c++) {
                int minPrev = Integer.MAX_VALUE;
                for (int x = 0; x < k; x++) {
                    if (x != c && dp[i-1][x] < minPrev) {
                        minPrev = dp[i-1][x];
                    }
                }
                dp[i][c] = costs[i][c] + minPrev;
            }
        }
        int result = Integer.MAX_VALUE;
        for (int c = 0; c < k; c++) {
            if (dp[n-1][c] < result) result = dp[n-1][c];
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] costs = {{1,5,3},{2,9,4},{15,7,6}};
        System.out.println(minCost(costs));
    }
}

Line Notes

int[][] dp = new int[n][k];Create dp table

dp[0][c] = costs[0][c];Initialize first house costs

for (int i = 1; i < n; i++)Iterate over houses

int minPrev = Integer.MAX_VALUE;Find minimal cost from previous house excluding current color

dp[i][c] = costs[i][c] + minPrev;Update dp with current cost plus minimal previous cost

return result;Return minimal total cost

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minCost(vector<vector<int>>& costs) {
    int n = costs.size();
    if (n == 0) return 0;
    int k = costs[0].size();
    vector<vector<int>> dp(n, vector<int>(k, 0));
    for (int c = 0; c < k; ++c) {
        dp[0][c] = costs[0][c];
    }
    for (int i = 1; i < n; ++i) {
        for (int c = 0; c < k; ++c) {
            int minPrev = INT_MAX;
            for (int x = 0; x < k; ++x) {
                if (x != c && dp[i-1][x] < minPrev) {
                    minPrev = dp[i-1][x];
                }
            }
            dp[i][c] = costs[i][c] + minPrev;
        }
    }
    int result = INT_MAX;
    for (int c = 0; c < k; ++c) {
        if (dp[n-1][c] < result) result = dp[n-1][c];
    }
    return result;
}

int main() {
    vector<vector<int>> costs = {{1,5,3},{2,9,4},{15,7,6}};
    cout << minCost(costs) << endl;
    return 0;
}

Line Notes

vector<vector<int>> dp(n, vector<int>(k, 0));Initialize dp table

dp[0][c] = costs[0][c];Set base case costs

for (int i = 1; i < n; ++i)Iterate over houses

int minPrev = INT_MAX;Find minimal cost from previous house excluding current color

dp[i][c] = costs[i][c] + minPrev;Update dp with current cost plus minimal previous cost

return result;Return minimal total cost

function minCost(costs) {
    const n = costs.length;
    if (n === 0) return 0;
    const k = costs[0].length;
    const dp = Array.from({length: n}, () => Array(k).fill(0));
    for (let c = 0; c < k; c++) {
        dp[0][c] = costs[0][c];
    }
    for (let i = 1; i < n; i++) {
        for (let c = 0; c < k; c++) {
            let minPrev = Infinity;
            for (let x = 0; x < k; x++) {
                if (x !== c && dp[i-1][x] < minPrev) {
                    minPrev = dp[i-1][x];
                }
            }
            dp[i][c] = costs[i][c] + minPrev;
        }
    }
    return Math.min(...dp[n-1]);
}

// Example usage
const costs = [[1,5,3],[2,9,4],[15,7,6]];
console.log(minCost(costs));

Line Notes

const dp = Array.from({length: n}, () => Array(k).fill(0));Initialize dp table

dp[0][c] = costs[0][c];Set base case costs

for (let i = 1; i < n; i++)Iterate over houses

let minPrev = Infinity;Find minimal cost from previous house excluding current color

dp[i][c] = costs[i][c] + minPrev;Update dp with current cost plus minimal previous cost

return Math.min(...dp[n-1]);Return minimal total cost

⏱

Complexity

TimeO(n*k*k)

SpaceO(n*k)

For each house and color, we scan all colors from previous house to find minimal cost

💡 For n=1000 and k=10, this is about 100,000 operations, efficient for interviews.

Interview Verdict: Accepted

This is the standard DP solution that balances clarity and efficiency.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i] depends only on dp[i-1], we can reduce space from O(n*k) to O(k) by reusing a single array.

Intuition

Keep track of minimal costs for the previous house in a 1D array and update it for the current house.

Algorithm

1. Initialize a 1D dp array with costs of the first house.
2. For each subsequent house, create a new dp array.
3. For each color, compute minimal cost as cost of current house plus minimal previous cost excluding same color.
4. Update dp array to new array after each house.
5. Return minimal value in dp after last house.

💡 This approach saves memory by not storing the entire dp table, only the last row is needed.

Recurrence:dp[c] = cost[i][c] + min_{x != c} dp_prev[x]

</>

Code

def minCost(costs):
    n = len(costs)
    if n == 0:
        return 0
    k = len(costs[0])
    dp = costs[0][:]

    for i in range(1, n):
        new_dp = [0]*k
        for c in range(k):
            min_prev = min(dp[x] for x in range(k) if x != c)
            new_dp[c] = costs[i][c] + min_prev
        dp = new_dp

    return min(dp)

# Example usage
if __name__ == '__main__':
    costs = [[1,5,3],[2,9,4],[15,7,6]]
    print(minCost(costs))

Line Notes

dp = costs[0][:]Initialize dp with first house costs

for i in range(1, n):Iterate over houses starting from second

min_prev = min(dp[x] for x in range(k) if x != c)Find minimal previous cost excluding current color

dp = new_dpUpdate dp to current house costs

public class PaintHouse {
    public static int minCost(int[][] costs) {
        int n = costs.length;
        if (n == 0) return 0;
        int k = costs[0].length;
        int[] dp = new int[k];
        System.arraycopy(costs[0], 0, dp, 0, k);

        for (int i = 1; i < n; i++) {
            int[] newDp = new int[k];
            for (int c = 0; c < k; c++) {
                int minPrev = Integer.MAX_VALUE;
                for (int x = 0; x < k; x++) {
                    if (x != c && dp[x] < minPrev) {
                        minPrev = dp[x];
                    }
                }
                newDp[c] = costs[i][c] + minPrev;
            }
            dp = newDp;
        }

        int result = Integer.MAX_VALUE;
        for (int c = 0; c < k; c++) {
            if (dp[c] < result) result = dp[c];
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] costs = {{1,5,3},{2,9,4},{15,7,6}};
        System.out.println(minCost(costs));
    }
}

Line Notes

int[] dp = new int[k];Initialize 1D dp array

System.arraycopy(costs[0], 0, dp, 0, k);Copy first house costs

for (int i = 1; i < n; i++)Iterate over houses

int minPrev = Integer.MAX_VALUE;Find minimal previous cost excluding current color

dp = newDp;Update dp to current house costs

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minCost(vector<vector<int>>& costs) {
    int n = costs.size();
    if (n == 0) return 0;
    int k = costs[0].size();
    vector<int> dp = costs[0];

    for (int i = 1; i < n; ++i) {
        vector<int> newDp(k, 0);
        for (int c = 0; c < k; ++c) {
            int minPrev = INT_MAX;
            for (int x = 0; x < k; ++x) {
                if (x != c && dp[x] < minPrev) {
                    minPrev = dp[x];
                }
            }
            newDp[c] = costs[i][c] + minPrev;
        }
        dp = newDp;
    }

    int result = INT_MAX;
    for (int c = 0; c < k; ++c) {
        if (dp[c] < result) result = dp[c];
    }
    return result;
}

int main() {
    vector<vector<int>> costs = {{1,5,3},{2,9,4},{15,7,6}};
    cout << minCost(costs) << endl;
    return 0;
}

Line Notes

vector<int> dp = costs[0];Initialize dp with first house costs

for (int i = 1; i < n; ++i)Iterate over houses

int minPrev = INT_MAX;Find minimal previous cost excluding current color

dp = newDp;Update dp to current house costs

function minCost(costs) {
    const n = costs.length;
    if (n === 0) return 0;
    const k = costs[0].length;
    let dp = costs[0].slice();

    for (let i = 1; i < n; i++) {
        const newDp = new Array(k).fill(0);
        for (let c = 0; c < k; c++) {
            let minPrev = Infinity;
            for (let x = 0; x < k; x++) {
                if (x !== c && dp[x] < minPrev) {
                    minPrev = dp[x];
                }
            }
            newDp[c] = costs[i][c] + minPrev;
        }
        dp = newDp;
    }

    return Math.min(...dp);
}

// Example usage
const costs = [[1,5,3],[2,9,4],[15,7,6]];
console.log(minCost(costs));

Line Notes

let dp = costs[0].slice();Initialize dp with first house costs

for (let i = 1; i < n; i++)Iterate over houses

let minPrev = Infinity;Find minimal previous cost excluding current color

dp = newDp;Update dp to current house costs

⏱

Complexity

TimeO(n*k*k)

SpaceO(k)

Only store costs for previous house, reducing space from O(n*k) to O(k)

💡 For large n, this saves significant memory while maintaining efficiency.

Interview Verdict: Accepted

This is the most space-efficient DP solution commonly expected in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bottom-up DP or space-optimized DP is usually best; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(k^n)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n*k*k)	O(n*k)	Possible for large n	Yes	Good for explaining optimization over brute force
3. Bottom-Up DP (Tabulation)	O(n*k*k)	O(n*k)	No	Yes	Standard solution to code
4. Space Optimized Bottom-Up DP	O(n*k*k)	O(k)	No	Yes, with extra bookkeeping	Best for memory efficiency, code if comfortable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem constraints and inputs.Explain the brute force recursive approach to show understanding of the problem.Introduce memoization to optimize recursion.Present bottom-up DP for clarity and efficiency.Finally, discuss space optimization to impress with memory efficiency.

Time Allocation

Clarify: 2min → Brute Force: 3min → Memoization: 5min → Tabulation: 5min → Space Optimization: 3min → Testing: 2min. Total ~20min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, code correctness, and clarity in explanation.

Common Follow-ups

• What if k is very large? → Use data structures to track minimal and second minimal costs efficiently.
• Can you reconstruct the color assignment? → Store choices during DP to backtrack.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves painting or coloring with adjacency constraints, 2) Minimize or maximize cost, 3) Choices depend on previous decisions, 4) Overlapping subproblems exist.

Signature Phrases

no two adjacent houses have the same colorminimum total costpaint each house with k colors

NOT This Pattern When

Problems without adjacency constraints or those solvable greedily are not this pattern.

Similar Problems

Paint Fence - similar adjacency constraints with fewer colorsHouse Robber II - adjacency constraints in linear structuresMinimum Cost to Paint Houses - variant with fixed k=3

Practice

1. Consider the following Python function implementing the bottom-up DP solution for the Burst Balloons problem. What is the value of dp[1][4] after the completion of the outer loops when the input is [3,1,5,8]?

def maxCoins(nums):
    n = len(nums)
    nums = [1] + nums + [1]
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    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]

easy

A. 15

B. 45

C. 40

D. 167

Solution

1. Step 1: Identify dp indices

   dp[1][4] corresponds to bursting balloons in nums indices 1 to 3 (original array indices 0 to 2), i.e. balloons [3,1,5].

2. Step 2: Calculate dp[1][4]

   By bursting last balloon k in (1,4), check k=2 and k=3: - k=2: dp[1][2] + nums[1]*nums[2]*nums[4] + dp[2][4] = 0 + 3*1*8 + 40 = 64 - k=3: dp[1][3] + nums[1]*nums[3]*nums[4] + dp[3][4] = 15 + 3*5*8 + 0 = 135 Max is 135, so dp[1][4] = 135 after the loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp[1][4] = 135 matches manual calculation [OK]

Hint: dp[i][j] stores max coins for bursting balloons between i and j [OK]

Common Mistakes:

• Confusing dp indices with nums indices
• Off-by-one errors in loops
• Miscomputing coins for k choices

2. Given the following code for the Dungeon Game problem, what is the value of dp[0][0] returned by calculateMinimumHP when called with dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]?

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = 1
        dp[m - 1][n] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, need)

        return dp[0][0]

easy

A. 7

B. 5

C. 3

D. 1

Solution

1. Step 1: Initialize dp boundaries

   dp[3][2] and dp[2][3] set to 1, others infinity.

2. Step 2: Compute dp bottom-up

   Calculate dp values from bottom-right to top-left considering dungeon values and ensuring health ≥1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known example output is 7 for this input [OK]

Hint: Trace dp from bottom-right to top-left [OK]

Common Mistakes:

• Off-by-one errors in dp indices
• Forgetting max(1, need)

3. You need to find the number of distinct ways to move from the top-left corner to the bottom-right corner of an m x n grid, moving only down or right at each step. Which algorithmic approach guarantees an efficient and optimal solution for this problem?

easy

A. Pure brute force recursion exploring all possible paths without memoization

B. Greedy algorithm that always moves towards the direction with fewer remaining steps

C. Dynamic Programming that builds solutions from smaller subproblems using a grid-based state representation

D. Divide and conquer by splitting the grid into quadrants and combining results

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all unique paths with only right and down moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable approach

   Dynamic Programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy or pure recursion which are either incorrect or inefficient.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP uses subproblem reuse -> optimal and efficient [OK]

Hint: Counting paths with overlapping subproblems -> DP [OK]

Common Mistakes:

• Thinking greedy can find all paths
• Using pure recursion without memoization

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Unique Paths problem on an m x n grid?

medium

A. O(m^2 * n^2)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m * n)

Solution

1. Step 1: Identify loops in the code

   The solution uses two nested loops: outer loop runs m-1 times, inner loop runs n-1 times.

2. Step 2: Calculate total operations

   Total operations ≈ (m-1) * (n-1) -> O(m * n). No extra hidden loops or recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over m and n -> O(m*n) [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing with recursion exponential time
• Forgetting loops multiply complexity

5. Suppose the polygon vertices can be reused multiple times in triangulation (i.e., vertices are not distinct points but can be repeated). How should the minimum score triangulation algorithm be modified to handle this?

hard

A. Use the same DP approach but allow k to iterate over all vertices, including i and j

B. Change the DP to a graph shortest path problem since reuse breaks polygon structure

C. Modify the DP to consider multisets of vertices and add memoization for repeated states

D. The problem becomes invalid as polygon vertices must be distinct; no modification possible

Solution

1. Step 1: Understand vertex reuse impact

   Reusing vertices breaks the polygon's simple structure; triangulation is no longer well-defined as a polygon.

2. Step 2: Identify correct approach

   The problem transforms into a graph problem where shortest paths or minimal cost cycles must be found, requiring a different algorithmic approach.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Reusing vertices invalidates polygon triangulation assumptions [OK]

Hint: Reusing vertices breaks polygon assumptions; DP no longer applies [OK]

Common Mistakes:

• Trying to reuse DP unchanged
• Ignoring polygon structure
• Assuming vertex reuse is trivial