Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleMicrosoftGoldman_Sachs

0/1 Knapsack Problem

Choose your preparation mode4 modes available
🎯
0/1 Knapsack Problem
mediumDPAmazonGoogleMicrosoft

Imagine you are a thief with a knapsack that can carry a limited weight. You want to maximize the total value of items you steal without exceeding the weight limit.

💡 This problem is a classic example of combinatorial optimization where you must decide whether to include or exclude each item. Beginners often struggle because the naive approach tries all subsets, which is exponential, and understanding how to optimize with dynamic programming requires grasping overlapping subproblems and optimal substructure.
📋
Problem Statement

Given n items, each with a weight and a value, determine the maximum total value of items you can include in a knapsack of capacity W. You can either include or exclude each item (no partial items allowed). Input: integer n, integer W, arrays weights and values of length n. Output: maximum value achievable without exceeding weight W.

1 ≤ n ≤ 10001 ≤ W ≤ 10^51 ≤ weights[i], values[i] ≤ 10^5
💡
Example
Input"n = 3, W = 50, weights = [10, 20, 30], values = [60, 100, 120]"
Output220

Choose items with weights 20 and 30 for total value 100 + 120 = 220 without exceeding capacity 50.

  • n = 1, W = weight of the single item → output is value if fits, else 0
  • All items heavier than W → output 0
  • All items fit into W → output sum of all values
  • W = 0 → output 0
🔁
Why DP?
Why greedy fails:

A greedy approach that picks items with the highest value or value-to-weight ratio first can fail. For example, items with high value but heavy weight might block better combinations of lighter items with better total value.

DP state:

dp[i][w] represents the maximum value achievable using the first i items with a knapsack capacity of w.

Recurrence:dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]) if weights[i-1] ≤ w else dp[i-1][w]

For each item, either skip it (dp[i-1][w]) or include it if it fits (dp[i-1][w - weight] + value), and take the better option.

⚠️
Common Mistakes
Not handling base cases correctly

Incorrect results or runtime errors

✅ Explicitly check for zero items or zero capacity

Iterating forwards in space optimized approach

Overcounting items, wrong answers

✅ Iterate backwards over capacities when updating dp array

Using 1-based indexing inconsistently

Index errors or off-by-one bugs

✅ Be consistent with indexing items and dp arrays

Not memoizing all parameters in recursion

Memoization ineffective, TLE

✅ Use both item index and capacity as memo keys

🧠
Brute Force (Pure Recursion)
💡 Starting with brute force helps understand the problem's combinatorial nature and why naive solutions are inefficient, setting the stage for dynamic programming.

Intuition

Try every combination of including or excluding each item recursively and pick the best total value that fits in the knapsack.

Algorithm

  1. Start from the first item and current capacity.
  2. Recursively explore two choices: include the item if it fits, or exclude it.
  3. Return the maximum value from these two choices.
  4. Base case: no items left or capacity zero.
💡 The recursion tree grows exponentially because each item doubles the number of subproblems.
Recurrence:f(i, w) = max(f(i-1, w), f(i-1, w - weights[i-1]) + values[i-1]) if weights[i-1] ≤ w else f(i-1, w)
</>
Code
def knapsack_recursive(i, w, weights, values):
    if i == 0 or w == 0:
        return 0
    if weights[i-1] > w:
        return knapsack_recursive(i-1, w, weights, values)
    else:
        return max(knapsack_recursive(i-1, w, weights, values),
                   knapsack_recursive(i-1, w - weights[i-1], weights, values) + values[i-1])

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    n = len(weights)
    print(knapsack_recursive(n, W, weights, values))
Line Notes
if i == 0 or w == 0:Base case: no items or no capacity means zero value
if weights[i-1] > w:If current item doesn't fit, skip it
return max(knapsack_recursive(i-1, w, weights, values),Option 1: exclude current item
knapsack_recursive(i-1, w - weights[i-1], weights, values) + values[i-1])Option 2: include current item and add its value
public class Knapsack {
    public static int knapsackRecursive(int i, int w, int[] weights, int[] values) {
        if (i == 0 || w == 0) return 0;
        if (weights[i - 1] > w) {
            return knapsackRecursive(i - 1, w, weights, values);
        } else {
            return Math.max(knapsackRecursive(i - 1, w, weights, values),
                            knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
        }
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        int n = weights.length;
        System.out.println(knapsackRecursive(n, W, weights, values));
    }
}
Line Notes
if (i == 0 || w == 0) return 0;Base case: no items or capacity means zero value
if (weights[i - 1] > w)Skip item if it doesn't fit
Math.max(knapsackRecursive(i - 1, w, weights, values),Exclude current item option
knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]Include current item option
#include <iostream>
#include <vector>
using namespace std;

int knapsackRecursive(int i, int w, const vector<int>& weights, const vector<int>& values) {
    if (i == 0 || w == 0) return 0;
    if (weights[i - 1] > w) {
        return knapsackRecursive(i - 1, w, weights, values);
    } else {
        return max(knapsackRecursive(i - 1, w, weights, values),
                   knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    int n = weights.size();
    cout << knapsackRecursive(n, W, weights, values) << endl;
    return 0;
}
Line Notes
if (i == 0 || w == 0) return 0;Base case: no items or capacity means zero value
if (weights[i - 1] > w)Skip item if it doesn't fit
max(knapsackRecursive(i - 1, w, weights, values),Exclude current item option
knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]Include current item option
function knapsackRecursive(i, w, weights, values) {
    if (i === 0 || w === 0) return 0;
    if (weights[i - 1] > w) {
        return knapsackRecursive(i - 1, w, weights, values);
    } else {
        return Math.max(knapsackRecursive(i - 1, w, weights, values),
                        knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
const n = weights.length;
console.log(knapsackRecursive(n, W, weights, values));
Line Notes
if (i === 0 || w === 0) return 0;Base case: no items or capacity means zero value
if (weights[i - 1] > w)Skip item if it doesn't fit
Math.max(knapsackRecursive(i - 1, w, weights, values),Exclude current item option
knapsackRecursive(i - 1, w - weights[i - 1], weights, values) + values[i - 1]Include current item option
⏱
Complexity
TimeO(2^n)
SpaceO(n) due to recursion stack

Each item has two choices, leading to 2^n combinations. The recursion stack depth is n.

💡 For n=20, this means over a million calls, which is too slow for interviews.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand before optimizing.

🧠
Top-Down Memoization
💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency while keeping the recursive structure.

Intuition

Use recursion but store results for each (i, w) state to avoid repeated work.

Algorithm

  1. Initialize a 2D cache for states (i, w).
  2. Recursively compute max value for each state, returning cached results if available.
  3. For each item, decide to include or exclude it if it fits.
  4. Return the cached maximum value for the full problem.
💡 Memoization prunes the recursion tree by remembering answers to subproblems.
Recurrence:Same as brute force: f(i, w) = max(f(i-1, w), f(i-1, w - weights[i-1]) + values[i-1]) if weights[i-1] ≤ w else f(i-1, w)
</>
Code
def knapsack_memo(i, w, weights, values, memo):
    if i == 0 or w == 0:
        return 0
    if (i, w) in memo:
        return memo[(i, w)]
    if weights[i-1] > w:
        memo[(i, w)] = knapsack_memo(i-1, w, weights, values, memo)
    else:
        memo[(i, w)] = max(knapsack_memo(i-1, w, weights, values, memo),
                           knapsack_memo(i-1, w - weights[i-1], weights, values, memo) + values[i-1])
    return memo[(i, w)]

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    n = len(weights)
    memo = {}
    print(knapsack_memo(n, W, weights, values, memo))
Line Notes
if (i, w) in memo:Check if result already computed to avoid recomputation
memo[(i, w)] = knapsack_memo(i-1, w, weights, values, memo)Store result when skipping item
memo[(i, w)] = max(...)Store result when choosing best of include/exclude
return memo[(i, w)]Return cached or newly computed result
import java.util.HashMap;
import java.util.Map;

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

    public static int knapsackMemo(int i, int w, int[] weights, int[] values) {
        if (i == 0 || w == 0) return 0;
        String key = i + "," + w;
        if (memo.containsKey(key)) return memo.get(key);
        int result;
        if (weights[i - 1] > w) {
            result = knapsackMemo(i - 1, w, weights, values);
        } else {
            result = Math.max(knapsackMemo(i - 1, w, weights, values),
                              knapsackMemo(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
        }
        memo.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        int n = weights.length;
        System.out.println(knapsackMemo(n, W, weights, values));
    }
}
Line Notes
if (memo.containsKey(key)) return memo.get(key);Return cached result if available
memo.put(key, result);Cache computed result for current state
if (weights[i - 1] > w)Skip item if it doesn't fit
Math.max(knapsackMemo(i - 1, w, weights, values),Choose max of exclude/include
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

unordered_map<string, int> memo;

int knapsackMemo(int i, int w, const vector<int>& weights, const vector<int>& values) {
    if (i == 0 || w == 0) return 0;
    string key = to_string(i) + "," + to_string(w);
    if (memo.find(key) != memo.end()) return memo[key];
    if (weights[i - 1] > w) {
        memo[key] = knapsackMemo(i - 1, w, weights, values);
    } else {
        memo[key] = max(knapsackMemo(i - 1, w, weights, values),
                        knapsackMemo(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
    return memo[key];
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    int n = weights.size();
    cout << knapsackMemo(n, W, weights, values) << endl;
    return 0;
}
Line Notes
if (memo.find(key) != memo.end()) return memo[key];Return cached result if available
memo[key] = knapsackMemo(i - 1, w, weights, values);Cache result when skipping item
memo[key] = max(...)Cache result when choosing best option
return memo[key];Return cached or computed result
const memo = new Map();

function knapsackMemo(i, w, weights, values) {
    if (i === 0 || w === 0) return 0;
    const key = i + ',' + w;
    if (memo.has(key)) return memo.get(key);
    let result;
    if (weights[i - 1] > w) {
        result = knapsackMemo(i - 1, w, weights, values);
    } else {
        result = Math.max(knapsackMemo(i - 1, w, weights, values),
                          knapsackMemo(i - 1, w - weights[i - 1], weights, values) + values[i - 1]);
    }
    memo.set(key, result);
    return result;
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
const n = weights.length;
console.log(knapsackMemo(n, W, weights, values));
Line Notes
if (memo.has(key)) return memo.get(key);Return cached result if available
memo.set(key, result);Cache computed result for reuse
if (weights[i - 1] > w)Skip item if it doesn't fit
Math.max(knapsackMemo(i - 1, w, weights, values),Choose max of exclude/include
⏱
Complexity
TimeO(n * W)
SpaceO(n * W) due to memoization cache and recursion stack

Each state (i, w) is computed once and stored, reducing exponential calls to polynomial.

💡 For n=1000 and W=1000, this means about 1 million states, which is feasible.
Interview Verdict: Accepted

Memoization makes the solution efficient enough for typical constraints.

🧠
Bottom-Up Tabulation
💡 Tabulation builds the solution iteratively from smaller subproblems, which is often easier to understand and avoids recursion overhead.

Intuition

Create a 2D dp table where each cell dp[i][w] stores the max value using first i items and capacity w, filling it row by row.

Algorithm

  1. Initialize a 2D dp array of size (n+1) x (W+1) with zeros.
  2. Iterate over items from 1 to n.
  3. For each capacity from 0 to W, decide to include or exclude the current item.
  4. Fill dp[i][w] with the maximum value achievable.
  5. Return dp[n][W] as the final answer.
💡 This approach systematically solves all subproblems in increasing order of items and capacities.
Recurrence:dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]) if weights[i-1] ≤ w else dp[i-1][w]
</>
Code
def knapsack_tabulation(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][W]

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    print(knapsack_tabulation(weights, values, W))
Line Notes
dp = [[0] * (W + 1) for _ in range(n + 1)]Initialize dp table with zeros for base cases
for i in range(1, n + 1):Iterate over items starting from 1
if weights[i - 1] <= w:Check if current item fits in capacity w
dp[i][w] = max(...)Choose max of excluding or including current item
public class Knapsack {
    public static int knapsackTabulation(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[][] dp = new int[n + 1][W + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        System.out.println(knapsackTabulation(weights, values, W));
    }
}
Line Notes
int[][] dp = new int[n + 1][W + 1];Create dp table with base cases initialized to zero
for (int i = 1; i <= n; i++) {Iterate over items
if (weights[i - 1] <= w) {Check if item fits in current capacity
dp[i][w] = Math.max(...)Choose max of excluding or including item
#include <iostream>
#include <vector>
using namespace std;

int knapsackTabulation(const vector<int>& weights, const vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    cout << knapsackTabulation(weights, values, W) << endl;
    return 0;
}
Line Notes
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));Initialize dp table with zeros
for (int i = 1; i <= n; i++) {Iterate over items
if (weights[i - 1] <= w) {Check if item fits
dp[i][w] = max(...)Choose max of excluding or including item
function knapsackTabulation(weights, values, W) {
    const n = weights.length;
    const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
console.log(knapsackTabulation(weights, values, W));
Line Notes
const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));Initialize 2D dp array with zeros
for (let i = 1; i <= n; i++) {Iterate over items
if (weights[i - 1] <= w) {Check if item fits in capacity
dp[i][w] = Math.max(...)Choose max of excluding or including item
⏱
Complexity
TimeO(n * W)
SpaceO(n * W)

We fill a table of size n by W once, each cell computed in O(1).

💡 For n=1000 and W=1000, this means about 1 million operations, which is efficient.
Interview Verdict: Accepted

This is the standard efficient solution for the 0/1 knapsack problem.

🧠
Space Optimized Bottom-Up
💡 Since dp[i][w] depends only on dp[i-1][...], we can reduce space from O(n*W) to O(W) by iterating backwards over capacities.

Intuition

Use a 1D dp array where dp[w] stores max value for capacity w, updating it in reverse order for each item.

Algorithm

  1. Initialize a 1D dp array of size W+1 with zeros.
  2. For each item, iterate capacities from W down to the item's weight.
  3. Update dp[w] as max of current dp[w] and dp[w - weight] + value.
  4. Return dp[W] as the maximum value.
💡 Backward iteration ensures we use results from the previous item iteration, preventing reuse of updated states.
Recurrence:dp[w] = max(dp[w], dp[w - weights[i-1]] + values[i-1]) for w ≥ weights[i-1]
</>
Code
def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# Driver code
if __name__ == '__main__':
    weights = [10, 20, 30]
    values = [60, 100, 120]
    W = 50
    print(knapsack_space_optimized(weights, values, W))
Line Notes
dp = [0] * (W + 1)Initialize 1D dp array for capacities
for i in range(n):Iterate over each item
for w in range(W, weights[i] - 1, -1):Iterate backwards over capacities to avoid reuse
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])Update dp[w] with max value including current item
public class Knapsack {
    public static int knapsackSpaceOptimized(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1];
        for (int i = 0; i < n; i++) {
            for (int w = W; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int W = 50;
        System.out.println(knapsackSpaceOptimized(weights, values, W));
    }
}
Line Notes
int[] dp = new int[W + 1];Initialize 1D dp array for capacities
for (int i = 0; i < n; i++) {Iterate over items
for (int w = W; w >= weights[i]; w--) {Iterate backwards over capacities
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);Update dp[w] with max value including current item
#include <iostream>
#include <vector>
using namespace std;

int knapsackSpaceOptimized(const vector<int>& weights, const vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

int main() {
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int W = 50;
    cout << knapsackSpaceOptimized(weights, values, W) << endl;
    return 0;
}
Line Notes
vector<int> dp(W + 1, 0);Initialize 1D dp array with zeros
for (int i = 0; i < n; i++) {Iterate over items
for (int w = W; w >= weights[i]; w--) {Iterate backwards over capacities
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);Update dp[w] with max value including current item
function knapsackSpaceOptimized(weights, values, W) {
    const n = weights.length;
    const dp = new Array(W + 1).fill(0);
    for (let i = 0; i < n; i++) {
        for (let w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

// Driver code
const weights = [10, 20, 30];
const values = [60, 100, 120];
const W = 50;
console.log(knapsackSpaceOptimized(weights, values, W));
Line Notes
const dp = new Array(W + 1).fill(0);Initialize 1D dp array for capacities
for (let i = 0; i < n; i++) {Iterate over items
for (let w = W; w >= weights[i]; w--) {Iterate backwards over capacities
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);Update dp[w] with max value including current item
⏱
Complexity
TimeO(n * W)
SpaceO(W)

We use a single dp array of size W+1 and update it for each item.

💡 This reduces memory usage significantly while maintaining time efficiency.
Interview Verdict: Accepted

This is the most space-efficient standard solution for 0/1 knapsack.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, code the bottom-up tabulation or space optimized approach for best balance of clarity and efficiency.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(2^n)O(n) recursion stackYes (deep recursion)YesMention only - never code
2. Top-Down MemoizationO(n * W)O(n * W) memo + recursion stackPossible for large nYesGood to explain optimization over brute force
3. Bottom-Up TabulationO(n * W)O(n * W)NoYesStandard approach to code
4. Space Optimized Bottom-UpO(n * W)O(W)NoNo (without extra tracking)Best for memory efficiency, mention if asked
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Clarify the problem constraints and inputs.Explain the brute force approach and its inefficiency.Introduce memoization to optimize recursion.Present bottom-up tabulation as an iterative alternative.Finally, discuss space optimization to reduce memory.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of recursion and dynamic programming, ability to optimize naive solutions, and clarity in explaining tradeoffs.

Common Follow-ups

  • What if item weights or values are very large? → Use value-based DP or approximation.
  • Can you reconstruct the selected items? → Use a parent pointer or backtrack dp table.
💡 These follow-ups test deeper understanding and ability to extend the solution.
🔍
Pattern Recognition

When to Use

1) Problem involves selecting items with weights and values; 2) Capacity constraint; 3) Decision to include/exclude each item; 4) Maximize total value.

Signature Phrases

maximize total value without exceeding capacitychoose items to include or exclude

NOT This Pattern When

Fractional Knapsack - allows partial items and is solved greedily

Similar Problems

Subset Sum Problem - special case with values = weightsPartition Equal Subset Sum - checks if subset sums to half totalUnbounded Knapsack - allows unlimited copies of items

Practice

(1/5)
1. The following code attempts to solve the Equal Partition problem using a 1D DP array. Which line contains a subtle bug that can cause incorrect results on some inputs?
def canPartition(nums):
    total = sum(nums)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(num, target + 1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]
medium
A. Line 2: Missing check if total is even before proceeding
B. Line 4: Initializing dp array with false instead of true
C. Line 6: Iterating forwards in dp array instead of backwards
D. Line 8: Returning dp[target] without verifying dp array correctness

Solution

  1. Step 1: Identify missing even check

    Line 2 does not check if total is even, but this causes no incorrect dp updates, only wasted computation.
  2. Step 2: Analyze dp iteration direction

    Line 6 iterates forwards, which causes reuse of updated dp values in the same iteration, leading to counting elements multiple times and incorrect results.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Backward iteration is required to avoid reusing updated dp values in the same iteration [OK]
Hint: DP must iterate backwards to avoid reuse in 1D array [OK]
Common Mistakes:
  • Iterating forwards in dp updates
  • Skipping even sum check
2. What is the time complexity of the bottom-up dynamic programming solution for the integer break problem shown below?
def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]
medium
A. O(n log n) time
B. O(n) time
C. O(2^n) time
D. O(n^2) time

Solution

  1. Step 1: Identify loops

    Outer loop runs from 2 to n (≈ n iterations). Inner loop runs from 1 to i (up to n iterations).
  2. Step 2: Calculate total operations

    Nested loops yield roughly 1 + 2 + ... + n ≈ n(n+1)/2 = O(n^2) operations.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Double nested loops with linear bounds -> quadratic time [OK]
Hint: Nested loops with linear bounds usually mean O(n²) [OK]
Common Mistakes:
  • Confusing with O(n) by ignoring inner loop
  • Thinking recursion stack adds exponential time here
3. The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?
medium
A. Line 3: Missing base case assignment dp[0] = 0
B. Line 2: dp initialization with infinity
C. Line 5: Outer loop from 1 to n
D. Line 7: Inner loop condition j*j <= i

Solution

  1. Step 1: Identify base case importance

    dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.
  2. Step 2: Analyze impact of missing dp[0] = 0

    Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing dp[0] base case breaks DP initialization [OK]
Hint: dp[0] must be zero to start DP correctly [OK]
Common Mistakes:
  • Forgetting dp[0] initialization
  • Misplacing loop boundaries
4. What is the time complexity of the space-optimized bottom-up DP solution for the Target Sum problem with input array length n and total sum S = sum(nums)?
medium
A. O(2^n) because all sign combinations are explored
B. O(n * S) because the DP iterates over n elements and sums from -S to S
C. O(n^2) because of nested loops over elements
D. O(n * log S) due to binary search on sums

Solution

  1. Step 1: Identify loops in the DP

    The outer loop runs n times, the inner loop runs over sums from -S to S, total 2S+1 states.
  2. Step 2: Calculate total operations

    Each iteration updates dp for each sum, so total time is O(n * S). Exponential 2^n is brute force, not DP.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP complexity depends on n and sum range, not exponential [OK]
Hint: DP iterates over n and sum range, not all subsets [OK]
Common Mistakes:
  • Confusing brute force 2^n with DP complexity
5. The following code attempts to solve the Target Sum problem using bottom-up DP with offset indexing. Which line contains a subtle bug that causes incorrect results on inputs containing zero?
medium
A. Line 12-15: Updating dp array in-place instead of using a separate next_dp
B. Line 6: dp[offset] = 1
C. Line 10: if dp[s] != 0:
D. Line 8: for num in nums:

Solution

  1. Step 1: Identify DP update method

    The code updates dp in-place during iteration over sums, causing double counting when num=0 or overlapping states.
  2. Step 2: Understand impact on zero values

    Zero does not change sum, so updating dp in-place doubles counts incorrectly. Using a separate next_dp array avoids this.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    In-place updates cause state reuse within iteration, breaking correctness [OK]
Hint: In-place dp updates cause double counting with zero values [OK]
Common Mistakes:
  • Not using a separate dp array for next iteration
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard