Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogleMicrosoftBloomberg

Coin Change (Minimum Coins)

Choose your preparation mode4 modes available
📋
Problem

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

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
Edge cases: 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)
</>
IDE
def coinChange(coins: list[int], amount: int) -> int:public int coinChange(int[] coins, int amount)int coinChange(vector<int>& coins, int amount)function coinChange(coins, amount)
def coinChange(coins, amount):
    # Write your solution here
    pass
class Solution {
    public int coinChange(int[] coins, int amount) {
        // Write your solution here
        return -1;
    }
}
#include <vector>
using namespace std;

int coinChange(vector<int>& coins, int amount) {
    // Write your solution here
    return -1;
}
function coinChange(coins, amount) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: -1 for amount=11 with coins=[1,2,5]Not considering all coin combinations or incorrect DP initialization.✅ Initialize dp array with large values and update dp[amt] = min(dp[amt], 1 + dp[amt - coin]) for all coins and amounts.
Wrong: 3 for amount=3 with coins=[2,5]Incorrectly assuming partial sums or using greedy approach that fails for impossible amounts.✅ Return -1 if dp[amount] remains infinity after DP computation.
Wrong: 1 for amount=3 with coins=[2]Confusing 0/1 knapsack with unbounded knapsack, allowing only one coin usage incorrectly.✅ Allow repeated use of coins by iterating amounts from coin to amount and updating dp accordingly.
Wrong: 4 for amount=7 with coins=[1,3,4]Greedy approach picking largest coin first without checking all combinations.✅ Use DP to consider all coins for each amount, not just greedy picks.
Wrong: TLE on large inputUsing brute force recursion without memoization or DP.✅ Implement bottom-up or top-down DP with memoization to achieve O(n*amount) time.
✓
Test Cases
t1_01basic
Input{"coins":[1,2,5],"amount":11}
Expected3

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

t1_02basic
Input{"coins":[1,3,4],"amount":6}
Expected2

6 = 3 + 3 or 4 + 1 + 1, minimum coins needed is 2 (3+3)

t2_01edge
Input{"coins":[1,2,5],"amount":0}
Expected0

Amount is zero, so no coins are needed.

t2_02edge
Input{"coins":[1],"amount":1}
Expected1

Single coin equals the amount, so minimum coins needed is 1.

t2_03edge
Input{"coins":[2,5],"amount":3}
Expected-1

No combination of coins 2 and 5 can sum to 3, so output is -1.

t3_01corner
Input{"coins":[1,3,4],"amount":7}
Expected2

7 = 4 + 3, minimum coins needed is 2. Greedy approach picking largest coin first (5 or 4) may fail if not careful.

t3_02corner
Input{"coins":[2],"amount":3}
Expected-1

Amount 3 cannot be formed with coin 2. Tests 0/1 knapsack confusion where coin can be used unlimited times.

t3_03corner
Input{"coins":[1,5,10],"amount":18}
Expected5

18 = 10 + 5 + 1 + 1 + 1, minimum coins needed is 3 (10 + 5 + 3*1). Tests off-by-one errors in DP indexing.

t4_01performance
Input{"coins":[1,2,5,10,20,50,100,200,500,1000,2000,5000],"amount":10000}
⏱ Performance - must finish in 2000ms

n=12 coins, amount=10000, O(n*amount) = 120,000 operations expected to complete within 2s.

Practice

(1/5)
1. Consider the following Python code for counting the number of ways to make change. What is the output when calling change(5, [1, 2, 5])?
easy
A. 5
B. 3
C. 4
D. 6

Solution

  1. Step 1: Initialize dp array

    dp = [1,0,0,0,0,0] since dp[0]=1.
  2. Step 2: Update dp for each coin

    For coin=1: dp becomes [1,1,1,1,1,1]; for coin=2: dp updates to [1,1,2,2,3,3]; for coin=5: dp updates to [1,1,2,2,3,4].
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    dp[5] = 4 matches known output [OK]
Hint: Trace dp updates coin by coin [OK]
Common Mistakes:
  • Off-by-one in dp indexing
  • Confusing permutations with combinations
2. You are given a list of positive integers and a target sum. You need to determine if there exists a subset of these integers that sums exactly to the target. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. A greedy algorithm that picks the largest numbers first until the sum is reached or exceeded.
B. A dynamic programming approach that builds a boolean table tracking achievable sums up to the target.
C. A depth-first search that tries all subsets without memoization.
D. A sorting-based two-pointer technique to find pairs that sum to the target.

Solution

  1. Step 1: Understand problem constraints

    The problem requires checking if any subset sums exactly to a target, which is a classic subset sum problem.
  2. Step 2: Identify algorithm that guarantees correctness

    Greedy and two-pointer approaches fail because they do not consider all subsets. DFS without memoization is correct but inefficient. Dynamic programming builds a table of achievable sums, ensuring all subsets are considered efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    DP tracks all sums up to target -> correct [OK]
Hint: Subset sum requires DP to track achievable sums [OK]
Common Mistakes:
  • Thinking greedy or sorting solves subset sum optimally
3. What is the time complexity of the optimal bottom-up dynamic programming solution for the Coin Change II problem with n coins and target amount amount?
medium
A. O(amount^2)
B. O(n + amount)
C. O(2^amount)
D. O(n * amount)

Solution

  1. Step 1: Identify loops in code

    Outer loop iterates over n coins, inner loop iterates over amount from coin to amount.
  2. Step 2: Calculate complexity

    Each dp[w] update is O(1), total updates are roughly n * amount, so time complexity is O(n * amount).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Nested loops over coins and amounts confirm O(n * amount) [OK]
Hint: Count nested loops and their ranges [OK]
Common Mistakes:
  • Confusing amount with n
  • Forgetting recursion stack space
  • Assuming quadratic in amount
4. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?
medium
A. Line 5: inner loop iterating backwards over amounts
B. Line 4: outer loop over coins
C. Line 2: dp initialization
D. Line 6: updating dp[w] with dp[w - coin]

Solution

  1. Step 1: Understand iteration order effect

    Iterating amounts backwards causes dp to count permutations, not combinations.
  2. Step 2: Identify bug line

    Line 5 iterates w from amount down to coin, which breaks combination counting logic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Forward iteration over amounts is required to count combinations correctly [OK]
Hint: Check direction of inner loop iteration [OK]
Common Mistakes:
  • Using backward iteration in 1D dp
  • Misplacing dp[0] initialization
5. Suppose the integer break problem is modified so that you can reuse the same integer parts multiple times (unbounded splits), and you want to find the maximum product. Which modification to the DP approach below correctly handles this variant?
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]
Options:
hard
A. Use a nested loop where for each i, iterate j from 1 to i and update dp[i] = max(dp[i], j * dp[i-j]) to allow reuse
B. Sort possible parts and greedily pick the largest part repeatedly to maximize product
C. Keep the same code but add memoization to avoid recomputation
D. Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j])

Solution

  1. Step 1: Understand reuse requirement

    Allowing reuse means dp[i] depends on dp[i-j] multiplied by j (or dp[j]) where j can be reused multiple times.
  2. Step 2: Modify DP update

    Updating dp[i] = max(dp[i], j * dp[i-j]) correctly models unbounded splits by combining current part j and best product for remaining i-j.
  3. Step 3: Evaluate other options

    Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j]) removes max(j, dp[j]) incorrectly; Keep the same code but add memoization to avoid recomputation adds memoization but doesn't change logic; Sort possible parts and greedily pick the largest part repeatedly to maximize product is greedy and fails on some inputs.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Unbounded knapsack style DP uses dp[i] = max(dp[i], j * dp[i-j]) [OK]
Hint: Unbounded knapsack uses dp[i] = max(dp[i], j * dp[i-j]) [OK]
Common Mistakes:
  • Using greedy approach
  • Not adjusting DP recurrence for reuse
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