Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleMicrosoftBloomberg

Coin Change (Minimum Coins)

Choose your preparation mode4 modes available
🎯
Coin Change (Minimum Coins)
mediumDPAmazonGoogleMicrosoft

Imagine you have an unlimited supply of coins of different denominations and you want to pay a certain amount using the fewest coins possible.

💡 This problem is a classic example of dynamic programming where beginners often struggle to see why greedy approaches fail and how to build solutions bottom-up or top-down with memoization.
📋
Problem Statement

Given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money, return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 2^31 - 10 ≤ amount ≤ 10^4
💡
Example
Input"coins = [1, 2, 5], amount = 11"
Output3

11 = 5 + 5 + 1, minimum coins needed is 3

Input"coins = [2], amount = 3"
Output-1

No combination of 2 can make 3

  • amount = 0 → output 0 (no coins needed)
  • coins = [1], amount = 0 → output 0 (zero amount)
  • coins = [1], amount = 1 → output 1 (single coin equals amount)
  • coins = [2, 5], amount = 3 → output -1 (impossible to form amount)
🔁
Why DP?
Why greedy fails:

Greedy fails because choosing the largest coin first does not always lead to the minimum number of coins. For example, amount=11 with coins=[1,5,7]: greedy picks 7 + 1 + 1 + 1 + 1 (5 coins), but optimal is 5 + 5 + 1 (3 coins).

DP state:

dp[i] represents the minimum number of coins needed to make amount i.

Recurrence:dp[i] = min(dp[i], 1 + dp[i - coin]) for each coin if i - coin >= 0

To find minimum coins for amount i, try each coin and add one coin to the minimum coins needed for amount i - coin, then take the minimum over all coins.

⚠️
Common Mistakes
Using greedy approach

Incorrect results for some inputs

✅ Use DP instead of greedy

Not handling amount=0 base case

Incorrect or infinite recursion

✅ Return 0 when amount is zero

Not checking for impossible amounts (returning infinity instead of -1)

Wrong output or runtime errors

✅ Return -1 if dp[amount] is infinity or max int

Using 2D DP unnecessarily

Wasted space and complexity

✅ Use 1D DP since only amount dimension matters

Not memoizing in top-down approach

TLE due to repeated calculations

✅ Add memo dictionary or map

🧠
Brute Force (Pure Recursion)
💡 This approach helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated calculations.

Intuition

Try every coin for the current amount and recursively find the minimum coins needed for the remaining amount.

Algorithm

  1. If amount is 0, return 0 because no coins are needed.
  2. For each coin, recursively compute minimum coins needed for amount - coin.
  3. Take the minimum among all recursive calls and add 1 for the current coin.
  4. If no solution found, return -1.
💡 The recursion tree grows exponentially because it tries all coin combinations without caching results.
Recurrence:f(amount) = min(1 + f(amount - coin)) for all coins where amount - coin >= 0
</>
Code
def coinChange(coins, amount):
    def dfs(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        res = float('inf')
        for coin in coins:
            res = min(res, 1 + dfs(rem - coin))
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

# Example usage
if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # Output: 3
Line Notes
def dfs(rem):Defines recursive helper to compute min coins for rem amount
if rem == 0:Base case: no coins needed for zero amount
if rem < 0:Invalid case: return infinity to exclude this path
for coin in coins:Try each coin to reduce the amount
res = min(res, 1 + dfs(rem - coin))Update minimum coins by choosing current coin plus recursive result
ans = dfs(amount)Start recursion from the target amount
return ans if ans != float('inf') else -1Return -1 if no solution found
import java.util.*;
public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        return dfs(coins, amount);
    }
    private static int dfs(int[] coins, int rem) {
        if (rem == 0) return 0;
        if (rem < 0) return Integer.MAX_VALUE;
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = dfs(coins, rem - coin);
            if (sub != Integer.MAX_VALUE) {
                res = Math.min(res, 1 + sub);
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}
Line Notes
public static int dfs(int[] coins, int rem)Recursive helper to find min coins for rem
if (rem == 0) return 0;Base case: zero coins needed for zero amount
if (rem < 0) return Integer.MAX_VALUE;Invalid path returns max value to exclude
for (int coin : coins)Try all coins to reduce amount
if (sub != Integer.MAX_VALUE)Check if recursive call returned valid result
res = Math.min(res, 1 + sub);Update minimum coins with current choice
return res;Return minimum coins found
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dfs(const vector<int>& coins, int rem) {
    if (rem == 0) return 0;
    if (rem < 0) return INT_MAX;
    int res = INT_MAX;
    for (int coin : coins) {
        int sub = dfs(coins, rem - coin);
        if (sub != INT_MAX) {
            res = min(res, 1 + sub);
        }
    }
    return res;
}

int coinChange(vector<int>& coins, int amount) {
    int ans = dfs(coins, amount);
    return ans == INT_MAX ? -1 : ans;
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}
Line Notes
int dfs(const vector<int>& coins, int rem)Recursive function to compute min coins for rem
if (rem == 0) return 0;Base case: zero coins needed
if (rem < 0) return INT_MAX;Invalid path returns max int to exclude
for (int coin : coins)Try each coin to reduce amount
if (sub != INT_MAX)Check if recursive call is valid
res = min(res, 1 + sub);Update minimum coins with current choice
return ans == INT_MAX ? -1 : ans;Return -1 if no solution
function coinChange(coins, amount) {
    function dfs(rem) {
        if (rem === 0) return 0;
        if (rem < 0) return Infinity;
        let res = Infinity;
        for (let coin of coins) {
            res = Math.min(res, 1 + dfs(rem - coin));
        }
        return res;
    }
    const ans = dfs(amount);
    return ans === Infinity ? -1 : ans;
}

// Example usage
console.log(coinChange([1,2,5], 11)); // 3
Line Notes
function dfs(rem)Recursive helper to find min coins for rem
if (rem === 0) return 0;Base case: zero coins needed
if (rem < 0) return Infinity;Invalid path returns Infinity to exclude
for (let coin of coins)Try all coins to reduce amount
res = Math.min(res, 1 + dfs(rem - coin));Update minimum coins with current choice
const ans = dfs(amount);Start recursion from amount
return ans === Infinity ? -1 : ans;Return -1 if no solution
⏱
Complexity
TimeO(S^n) where S is amount and n is number of coins due to exponential recursion
SpaceO(S) recursion stack depth

Each amount calls all coins recursively leading to exponential calls

💡 For amount=20 and 3 coins, this can lead to millions of calls, making it impractical.
Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠
Top-Down Memoization
💡 Memoization caches results of subproblems to avoid repeated work, drastically improving efficiency over brute force.

Intuition

Use recursion but store results for each amount so that repeated calls return cached answers instantly.

Algorithm

  1. Initialize a memo dictionary to store minimum coins for each amount.
  2. If amount is 0, return 0.
  3. If amount is negative, return infinity.
  4. If amount is in memo, return stored result.
  5. For each coin, recursively compute minimum coins for amount - coin and update minimum.
  6. Store and return the minimum coins for current amount.
💡 Memoization reduces exponential calls to polynomial by caching results.
Recurrence:f(amount) = min(1 + f(amount - coin)) for all coins, with memoization
</>
Code
def coinChange(coins, amount):
    memo = {}
    def dfs(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        if rem in memo:
            return memo[rem]
        res = float('inf')
        for coin in coins:
            res = min(res, 1 + dfs(rem - coin))
        memo[rem] = res
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # 3
Line Notes
memo = {}Initialize cache to store results for amounts
if rem in memo:Return cached result if available
memo[rem] = resStore computed result to avoid recomputation
res = min(res, 1 + dfs(rem - coin))Try all coins and pick minimum
ans = dfs(amount)Start recursion from target amount
return ans if ans != float('inf') else -1Return -1 if no solution
import java.util.*;
public class CoinChange {
    private static Map<Integer, Integer> memo = new HashMap<>();
    public static int coinChange(int[] coins, int amount) {
        int res = dfs(coins, amount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    private static int dfs(int[] coins, int rem) {
        if (rem == 0) return 0;
        if (rem < 0) return Integer.MAX_VALUE;
        if (memo.containsKey(rem)) return memo.get(rem);
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = dfs(coins, rem - coin);
            if (sub != Integer.MAX_VALUE) {
                res = Math.min(res, 1 + sub);
            }
        }
        memo.put(rem, res);
        return res;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}
Line Notes
private static Map<Integer, Integer> memo = new HashMap<>();Cache results for amounts
if (memo.containsKey(rem)) return memo.get(rem);Return cached result if present
memo.put(rem, res);Store computed result
res = Math.min(res, 1 + sub);Try all coins and update minimum
return res;Return minimum coins for rem
#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

unordered_map<int,int> memo;

int dfs(const vector<int>& coins, int rem) {
    if (rem == 0) return 0;
    if (rem < 0) return INT_MAX;
    if (memo.count(rem)) return memo[rem];
    int res = INT_MAX;
    for (int coin : coins) {
        int sub = dfs(coins, rem - coin);
        if (sub != INT_MAX) {
            res = min(res, 1 + sub);
        }
    }
    memo[rem] = res;
    return res;
}

int coinChange(vector<int>& coins, int amount) {
    int ans = dfs(coins, amount);
    return ans == INT_MAX ? -1 : ans;
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}
Line Notes
unordered_map<int,int> memo;Cache for storing results
if (memo.count(rem)) return memo[rem];Return cached result if exists
memo[rem] = res;Store computed minimum coins
res = min(res, 1 + sub);Try all coins and update minimum
return ans == INT_MAX ? -1 : ans;Return -1 if no solution
function coinChange(coins, amount) {
    const memo = new Map();
    function dfs(rem) {
        if (rem === 0) return 0;
        if (rem < 0) return Infinity;
        if (memo.has(rem)) return memo.get(rem);
        let res = Infinity;
        for (let coin of coins) {
            res = Math.min(res, 1 + dfs(rem - coin));
        }
        memo.set(rem, res);
        return res;
    }
    const ans = dfs(amount);
    return ans === Infinity ? -1 : ans;
}

console.log(coinChange([1,2,5], 11)); // 3
Line Notes
const memo = new Map();Cache results for amounts
if (memo.has(rem)) return memo.get(rem);Return cached result if available
memo.set(rem, res);Store computed result
res = Math.min(res, 1 + dfs(rem - coin));Try all coins and update minimum
return ans === Infinity ? -1 : ans;Return -1 if no solution
⏱
Complexity
TimeO(amount * n) where n is number of coins due to memoization
SpaceO(amount) for memo and recursion stack

Each amount is computed once and stored, reducing exponential calls to linear in amount

💡 For amount=20 and 3 coins, this reduces calls from millions to about 60.
Interview Verdict: Accepted

This approach is efficient enough for typical interview constraints and demonstrates DP memoization well.

🧠
Bottom-Up Tabulation (Iterative DP)
💡 This approach builds the solution from the smallest subproblems up to the target amount, avoiding recursion and making the process clearer and often faster.

Intuition

Create a dp array where dp[i] stores minimum coins needed for amount i, and fill it iteratively from 0 to amount.

Algorithm

  1. Initialize dp array of size amount+1 with infinity, except dp[0] = 0.
  2. For each amount i from 1 to amount, try each coin.
  3. If coin <= i, update dp[i] = min(dp[i], 1 + dp[i - coin]).
  4. After filling dp, if dp[amount] is infinity, return -1; else return dp[amount].
💡 This approach ensures all subproblems are solved once in a systematic order.
Recurrence:dp[i] = min(dp[i], 1 + dp[i - coin]) for all coins where i - coin >= 0
</>
Code
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # 3
Line Notes
dp = [float('inf')] * (amount + 1)Initialize dp array with infinity to represent unreachable amounts
dp[0] = 0Zero coins needed to make amount zero
for i in range(1, amount + 1)Iterate over all amounts from 1 to target
if coin <= iOnly consider coins that can fit into current amount
dp[i] = min(dp[i], 1 + dp[i - coin])Update dp[i] with minimum coins using current coin
return dp[amount] if dp[amount] != float('inf') else -1Return result or -1 if no solution
import java.util.*;
public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}
Line Notes
int[] dp = new int[amount + 1];Create dp array for amounts
Arrays.fill(dp, Integer.MAX_VALUE);Initialize dp with max value to represent unreachable
dp[0] = 0;Zero coins needed for amount zero
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)Check coin fits and subproblem is solvable
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];Return result or -1
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}
Line Notes
vector<int> dp(amount + 1, INT_MAX);Initialize dp array with max int
dp[0] = 0;Zero coins needed for zero amount
if (coin <= i && dp[i - coin] != INT_MAX)Check coin fits and subproblem solvable
dp[i] = min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins
return dp[amount] == INT_MAX ? -1 : dp[amount];Return result or -1
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1,2,5], 11)); // 3
Line Notes
const dp = new Array(amount + 1).fill(Infinity);Initialize dp array with Infinity
dp[0] = 0;Zero coins needed for zero amount
if (coin <= i)Check coin fits into current amount
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins
return dp[amount] === Infinity ? -1 : dp[amount];Return result or -1
⏱
Complexity
TimeO(amount * n) where n is number of coins
SpaceO(amount) for dp array

Each amount is computed once by checking all coins

💡 For amount=20 and 3 coins, about 60 operations, very efficient.
Interview Verdict: Accepted

This is the standard optimal DP solution for this problem in interviews.

🧠
Space Optimized Bottom-Up (1D DP)
💡 Since the problem only depends on previous states in a 1D array, we can optimize space by using a single dp array without extra dimensions.

Intuition

Use a single dp array to store minimum coins for each amount and update it iteratively.

Algorithm

  1. Initialize dp array of size amount+1 with infinity, except dp[0] = 0.
  2. Iterate amounts from 1 to amount.
  3. For each coin, if coin <= current amount, update dp[current amount] with min of current and 1 + dp[current amount - coin].
  4. Return dp[amount] if reachable, else -1.
💡 This approach uses minimal memory while maintaining the same logic as tabulation.
Recurrence:dp[i] = min(dp[i], 1 + dp[i - coin]) for all coins where i - coin >= 0
</>
Code
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

if __name__ == '__main__':
    print(coinChange([1,2,5], 11))  # 3
Line Notes
dp = [float('inf')] * (amount + 1)Initialize dp with infinity to represent unreachable amounts
dp[0] = 0Zero coins needed for zero amount
for i in range(1, amount + 1)Iterate over all amounts
if coin <= iCheck if coin can be used for current amount
dp[i] = min(dp[i], 1 + dp[i - coin])Update dp[i] with minimum coins
return dp[amount] if dp[amount] != float('inf') else -1Return result or -1
import java.util.*;
public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1,2,5}, 11)); // 3
    }
}
Line Notes
int[] dp = new int[amount + 1];Create dp array for amounts
Arrays.fill(dp, Integer.MAX_VALUE);Initialize dp with max value
dp[0] = 0;Zero coins needed for zero amount
if (coin <= i && dp[i - coin] != Integer.MAX_VALUE)Check coin fits and subproblem solvable
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];Return result or -1
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1,2,5};
    cout << coinChange(coins, 11) << endl; // 3
    return 0;
}
Line Notes
vector<int> dp(amount + 1, INT_MAX);Initialize dp array with max int
dp[0] = 0;Zero coins needed for zero amount
if (coin <= i && dp[i - coin] != INT_MAX)Check coin fits and subproblem solvable
dp[i] = min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins
return dp[amount] == INT_MAX ? -1 : dp[amount];Return result or -1
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1,2,5], 11)); // 3
Line Notes
const dp = new Array(amount + 1).fill(Infinity);Initialize dp with Infinity
dp[0] = 0;Zero coins needed for zero amount
if (coin <= i)Check coin fits into current amount
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);Update dp[i] with minimum coins
return dp[amount] === Infinity ? -1 : dp[amount];Return result or -1
⏱
Complexity
TimeO(amount * n) where n is number of coins
SpaceO(amount) for dp array

Same as tabulation but uses minimal memory

💡 This is the most memory-efficient standard DP solution.
Interview Verdict: Accepted

This is the preferred approach in interviews for its clarity and efficiency.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, coding bottom-up tabulation or memoization is best; brute force is only for explanation.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceExponentialO(amount) recursion stackYes (deep recursion)NoMention only - never code
2. Top-Down MemoizationO(amount * n)O(amount) memo + recursion stackPossible for large amountYes with extra trackingGood for explaining optimization
3. Bottom-Up TabulationO(amount * n)O(amount)NoYes with extra trackingPreferred approach to code
4. Space Optimized Bottom-UpO(amount * n)O(amount)NoYes with extra trackingMention as optimization
💼
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

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up tabulation as the optimal iterative solution.Step 5: Optionally mention space optimization for memory efficiency.Step 6: Code the chosen approach carefully and test with examples.

Time Allocation

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

What the Interviewer Tests

Understanding of recursion and DP, ability to optimize naive solutions, clarity in explaining tradeoffs, and clean coding skills.

Common Follow-ups

  • What if you want to count the number of ways to make the amount? → Use a different DP formulation.
  • How to reconstruct the coins used? → Store choices during DP and backtrack.
💡 These follow-ups test deeper understanding of DP variations and solution reconstruction.
🔍
Pattern Recognition

When to Use

1) Problem asks for minimum or maximum using unlimited items, 2) Choices can be repeated, 3) Problem can be broken into smaller subproblems by reducing amount, 4) Overlapping subproblems exist.

Signature Phrases

'fewest number of coins''unlimited supply of coins''make up that amount'

NOT This Pattern When

Problems with limited items or no repetition are 0/1 knapsack, not unbounded.

Similar Problems

Coin Change 2 - counts number of ways instead of minimum coinsRod Cutting - similar unbounded knapsack with lengthsMinimum Number of Squares - similar DP minimization problem

Practice

(1/5)
1. You need to split a positive integer n into at least two positive integers such that the product of these integers is maximized. Which algorithmic approach guarantees finding the optimal solution efficiently?
easy
A. Pure brute force recursion exploring all partitions without memoization
B. A greedy approach that always cuts the integer into 3s and 2s
C. Dynamic programming using bottom-up tabulation with state representing maximum product for each integer up to n
D. Divide and conquer by splitting the integer into two halves recursively without caching results

Solution

  1. Step 1: Understand problem structure

    The problem requires maximizing product by splitting an integer into parts, which naturally fits a DP approach where subproblems represent maximum product for smaller integers.
  2. Step 2: Evaluate options

    Greedy (always cutting 3s) fails on some inputs; brute force recursion is correct but inefficient; divide and conquer without memoization repeats work. Bottom-up DP tabulation efficiently computes all subproblems and combines results.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    DP tabulation ensures optimal substructure and overlapping subproblems [OK]
Hint: DP tabulation handles overlapping subproblems optimally [OK]
Common Mistakes:
  • Believing greedy always works for integer break
  • Ignoring memoization in recursion
2. Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?
easy
A. 1
B. 0
C. 2
D. 3

Solution

  1. Step 1: Calculate total and half

    Total = 6, half = 3. dp array size = 4, dp[0] = true initially.
  2. Step 2: Update dp for each stone

    For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.
  3. Step 3: Find largest w ≤ half with dp[w] = true

    dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]
Hint: Check dp array for sums up to half total [OK]
Common Mistakes:
  • Returning total instead of minimal difference
  • Off-by-one error in dp indexing
  • Not iterating backwards in dp update
3. Consider the following Python function implementing the DP with bitmask tabulation approach for partitioning an array into k equal sum subsets. What is the return value when called with nums = [1, 2, 3, 4] and k = 2?
from typing import List

def canPartitionKSubsets(nums: List[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                if dp[next_mask] == -1:
                    dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0
easy
A. True
B. False
C. Raises an exception due to index error
D. Returns None

Solution

  1. Step 1: Calculate total and target

    Sum is 10, k=2, target subset sum = 5.
  2. Step 2: Trace dp updates

    DP explores subsets; for example, {1,4} and {2,3} both sum to 5, so dp[(1<<4)-1] = 0, returning True.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Partition exists: [1,4] and [2,3] [OK]
Hint: Sum divisible by k and dp final state 0 means partition possible [OK]
Common Mistakes:
  • Confusing dp array indexing or bitmask operations
  • Forgetting to check if largest element exceeds target
4. Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?
easy
A. 1
B. 3
C. 0
D. 2

Solution

  1. Step 1: Trace initial dp array

    total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)
  2. Step 2: Process num=1 and num=2 updating dp

    After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Two ways: +1-2 and -1+2 sum to 1 [OK]
Hint: Offset indexing maps sums to dp indices [OK]
Common Mistakes:
  • Off-by-one errors in indexing dp array
5. What is the time complexity of the space-optimized bottom-up 0/1 Knapsack algorithm when there are n items and the knapsack capacity is W?
medium
A. O(2^n)
B. O(n + W)
C. O(n * W)
D. O(n * log W)

Solution

  1. Step 1: Identify loops in the algorithm

    The algorithm has an outer loop over n items and an inner loop over capacities from W down to the item's weight, which can be up to W iterations.
  2. Step 2: Calculate total operations

    Multiplying the loops gives O(n * W) time complexity. Recursive brute force is exponential, and linear or logarithmic complexities are incorrect here.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Nested loops over n and W -> O(n * W) [OK]
Hint: Nested loops over items and capacity -> O(n * W) [OK]
Common Mistakes:
  • Confusing recursion stack space with time complexity.
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