Coin Change (Minimum Coins)

📋

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
}

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

Focus on handling base cases and small inputs correctly.

Think about common pitfalls like greedy traps and usage constraints.

Optimize your solution to avoid exponential time complexity.

t1_01basic

Input{"coins":[1,2,5],"amount":11}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Think about building the solution from smaller amounts up to the target amount.

💡 Use dynamic programming to store minimum coins needed for each amount up to 11.

💡 For each amount, try each coin and update the minimum coins if using that coin reduces the count.

Why it failed: Failed basic case: likely not considering all coin combinations or incorrect DP recurrence. Fix by ensuring dp[amt] = min(dp[amt], 1 + dp[amt - coin]) for all coins where coin <= amt.

✓ Correctly computes minimum coins for standard input.

t1_02basic

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

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Try to find combinations that sum to 6 using the fewest coins.

💡 Check all coins for each sub-amount and update minimum coins accordingly.

💡 Remember that coins can be used unlimited times, so consider repeated use of the same coin.

Why it failed: Incorrect output due to not handling unbounded usage of coins properly. Fix by allowing repeated use of coins in DP updates.

✓ Handles unbounded coin usage correctly for minimum coins.

t2_01edge

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

Expected0

⏱ Performance - must finish in 2000ms

Amount is zero, so no coins are needed.

💡 Check the base case where amount is zero.

💡 Minimum coins needed for amount zero should be zero.

💡 Initialize dp[0] = 0 to handle this case.

Why it failed: Fails zero amount case by not initializing dp[0] = 0. Fix by setting dp[0] = 0 before DP iteration.

✓ Correctly returns 0 when amount is zero.

t2_02edge

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Test with only one coin equal to the amount.

💡 DP should recognize direct match without extra coins.

💡 Ensure dp[coin] = 1 for coin in coins if coin <= amount.

Why it failed: Fails single coin exact match by not updating dp[coin] correctly. Fix by initializing dp[coin] = 1 for coins <= amount.

✓ Correctly handles single coin equal to amount.

t2_03edge

Input{"coins":[2,5],"amount":3}

Expected-1

⏱ Performance - must finish in 2000ms

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

💡 Consider amounts that cannot be formed by given coins.

💡 DP should detect unreachable amounts and return -1.

💡 Initialize dp array with a large number and check if dp[amount] was updated.

Why it failed: Fails impossible amount case by returning a number instead of -1. Fix by returning -1 if dp[amount] remains infinity.

✓ Correctly returns -1 when amount cannot be formed.

t3_01corner

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

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Beware of greedy approaches that pick largest coin first.

💡 DP ensures all combinations are considered, not just greedy picks.

💡 Check all coins for each amount to find minimum coins, not just largest coin.

Why it failed: Fails greedy trap by returning 3 (4+1+1+1) instead of 2. Fix by using DP to consider all coin combinations, not greedy selection.

✓ Avoids greedy trap and finds true minimum coins.

t3_02corner

Input{"coins":[2],"amount":3}

Expected-1

⏱ Performance - must finish in 2000ms

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

💡 Remember coins can be used unlimited times (unbounded knapsack).

💡 Check if solution incorrectly treats coins as 0/1 usage.

💡 Ensure DP allows repeated use of coins for all amounts.

Why it failed: Fails 0/1 vs unbounded confusion by returning 1 (incorrectly using coin once). Fix by allowing repeated use of coins in DP updates.

✓ Correctly handles unbounded usage and returns -1 when impossible.

t3_03corner

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

Expected5

⏱ Performance - must finish in 2000ms

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

💡 Check DP array indexing carefully to avoid off-by-one errors.

💡 Ensure dp array size covers all amounts up to target.

💡 Verify dp updates use correct indices for amounts and coins.

Why it failed: Fails off-by-one error by returning incorrect minimum coins. Fix by correctly indexing dp array and updating dp[amt] using dp[amt - coin].

✓ Handles indexing correctly and returns accurate minimum coins.

t4_01performance

Input{"coins":[1,2,5,10,20,50,100,200,500,1000,2000,5000],"amount":10000}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Use bottom-up DP with O(n*amount) time complexity.

💡 Avoid exponential recursion to prevent TLE.

💡 Optimize space by using 1D dp array instead of 2D.

Why it failed: TLE due to exponential brute force recursion. Fix by implementing DP with O(n*amount) complexity.

✓ Efficient DP solution runs within time limits.

Practice

1. Given the following code, what is the output when coins = [1, 2, 5] and amount = 5?

def count_ways_space_opt(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

coins = [1, 2, 5]
amount = 5
print(count_ways_space_opt(coins, amount))

easy

A. 4

B. 7

C. 5

D. 6

Solution

1. Step 1: Trace dp array updates for each coin

   Start dp = [1,0,0,0,0,0]. After coin=1, dp = [1,1,1,1,1,1]. After coin=2, dp = [1,1,2,2,3,3]. After coin=5, dp = [1,1,2,2,3,6].

2. Step 2: Confirm dp[5] value

   dp[5] = 6, representing 6 ways to make amount 5 with coins [1,2,5].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual dp tracing matches output 6 [OK]

Hint: DP accumulates counts incrementally per coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Miscounting after last coin iteration
• Confusing permutations with combinations

2. The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?

def integer_break(n):
    dp = [0] * n
    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. Line 3: dp[1] = 1 base case initialization

B. Line 2: dp array size is n instead of n+1

C. Line 5: Outer loop range from 2 to n+1

D. Line 7: Using max(j, dp[j]) instead of just dp[j]

Solution

1. Step 1: Check dp array size

   dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.

2. Step 2: Consequences of wrong size

   Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp array must be size n+1 to safely index up to n [OK]

Hint: Check array size matches max index accessed [OK]

Common Mistakes:

• Forgetting dp size off-by-one
• Misplacing base case initialization

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

4. Suppose now you want to count the number of ways to make change but coins can be used at most once each (no reuse). Which modification to the DP approach correctly solves this variant?

hard

A. Use 1D DP iterating amounts forwards but reset dp array after each coin

B. Use 2D DP with dp[i][w] representing ways using first i coins for amount w, iterating amounts forwards

C. Use the same 1D DP but iterate amounts backwards from amount down to coin value

D. Use greedy approach picking largest coins first until amount is reached

Solution

1. Step 1: Understand no reuse constraint

   Each coin can be used once, so combinations must not count repeated usage of the same coin.

2. Step 2: Modify DP iteration order

   Iterating amounts backwards in 1D DP ensures each coin contributes only once per amount, preventing reuse.

3. Step 3: Confirm correctness

   This approach correctly counts combinations without reuse, unlike forward iteration which allows multiple usage.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backward iteration in 1D DP enforces single usage per coin [OK]

Hint: Backward iteration prevents coin reuse in 1D DP [OK]

Common Mistakes:

• Using forward iteration allows unlimited reuse
• Resetting dp array loses accumulated counts
• Greedy approach misses many combinations

5. Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant?

hard

A. Change the inner loop to iterate forwards from num to S, allowing reuse of the same number multiple times.

B. Keep the inner loop iterating backwards from S to num, as in the 0/1 subset sum problem.

C. Use a recursive brute force approach without memoization to handle multiple uses.

D. Sort the input array and apply a greedy approach picking largest numbers first.

Solution

1. Step 1: Understand difference between 0/1 and unbounded knapsack

   In unbounded knapsack, items can be reused multiple times, so dp updates must allow reuse within the same iteration.

2. Step 2: Modify iteration direction

   Iterating forwards allows dp[w] to use dp[w - num] updated in the same iteration, enabling multiple uses of num.

3. Step 3: Confirm correctness

   Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded variant.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward iteration enables multiple uses -> correct for unbounded knapsack [OK]

Hint: Unbounded knapsack requires forward iteration to allow reuse [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack
• Trying greedy or brute force without memoization