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

3. You are given a printer that can print a continuous substring of identical characters in one turn. Given a string, you want to find the minimum number of turns needed to print the entire string. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming over intervals with string compression and merging states

B. Greedy approach printing each character separately from left to right

C. Simple recursion without memoization or compression

D. Sliding window technique to find longest repeated substrings

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing turns to print a string where each turn prints a continuous block of identical characters.

2. Step 2: Identify suitable algorithmic pattern

   Greedy or sliding window approaches fail to merge overlapping prints optimally. Pure recursion is inefficient. Interval DP with string compression and merging states captures overlapping subproblems and optimizes turns.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interval DP with compression is known optimal [OK]

Hint: Interval DP with compression merges overlapping prints [OK]

Common Mistakes:

• Assuming greedy printing each char separately is optimal

4. What is the time complexity of the space-optimized bottom-up DP solution for the Cheapest Flights Within K Stops problem, given n cities, E flights, and maximum K stops?

medium

A. O(K * E) because each iteration relaxes all edges up to K+1 times

B. O(n^3) due to nested loops over cities and stops

C. O(E * log n) similar to Dijkstra's algorithm

D. O(n * K^2) due to dynamic programming over stops and cities

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop runs K+1 times, and the inner loop iterates over all E flights to relax edges.

2. Step 2: Calculate total complexity

   Each iteration processes E edges, so total time is O(K * E). No nested loops over n^2 or log factors appear.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Algorithm iterates over edges K+1 times [OK]

Hint: Outer loop K+1 times, inner loop over E edges [OK]

Common Mistakes:

• Confusing E with n^2
• Assuming Dijkstra complexity
• Counting recursion stack space

5. Suppose the problem is modified so that you can move right, down, or diagonally down-right, still avoiding obstacles. Which of the following changes to the space-optimized DP approach correctly accounts for the new diagonal move?

hard

A. Modify dp[j] += dp[j-1] to dp[j] += dp[j-1] + dp[j] without extra storage.

B. Use a 2D dp array where dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], updating in row-major order.

C. Add dp[j-1] and dp[j] plus dp[j-1] from previous row, requiring a 2D dp array to track diagonal paths.

D. Keep 1D dp array but add dp[j-1] twice to account for diagonal moves.

Solution

1. Step 1: Understand diagonal dependency

   Diagonal move depends on dp[i-1][j-1], which cannot be tracked with only 1D dp array updated in-place.

2. Step 2: Correct approach

   Use 2D dp array to store counts for all cells, updating dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], ensuring all dependencies are available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Diagonal requires previous row and previous column info simultaneously [OK]

Hint: Diagonal moves require 2D dp to track previous row and column [OK]

Common Mistakes:

• Trying to reuse 1D dp without extra storage
• Double counting paths
• Ignoring diagonal dependency