Coin Change

Difficulty: Medium Source: NeetCode

Problem

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

You may assume that you have an infinite number of each kind of coin.

Example 1: Input: coins = [1,5,11], amount = 15 Output: 3 (11 + 1 + … wait, 11+1+1+1+1 = 5 coins… actually 5+5+5 = 3 coins)

Example 2: Input: coins = [1,5,11], amount = 15 Output: 3 (5 + 5 + 5)

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

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

Prerequisites

Before attempting this problem, you should be comfortable with:

• Unbounded Knapsack — using each item (coin) unlimited times
• BFS on Implicit Graph — treating amounts as nodes and coins as edges
• DP Arrays — building up optimal subproblems for each sub-amount

1. Brute Force (Recursion)

Intuition

At each amount, try subtracting every coin and recurse. The minimum of all valid recursive calls plus 1 is the answer. Without memoization, this explores an exponential number of combinations.

Algorithm

1. dp(amount) = fewest coins to make amount.
2. Base case: dp(0) = 0.
3. Recursive case: dp(a) = 1 + min(dp(a - coin) for coin in coins if coin <= a).

Solution

def coinChange_brute(coins, amount):
    memo = {}

    def dp(a):
        if a == 0:
            return 0
        if a < 0:
            return float('inf')
        if a in memo:
            return memo[a]
        result = 1 + min(dp(a - coin) for coin in coins)
        memo[a] = result
        return result

    ans = dp(amount)
    return ans if ans != float('inf') else -1


print(coinChange_brute([1, 5, 11], 15))  # 3
print(coinChange_brute([2], 3))          # -1
print(coinChange_brute([1, 2, 5], 11))  # 3  (5+5+1)
print(coinChange_brute([1], 0))          # 0

Complexity

• Time: O(amount * len(coins)) with memoization
• Space: O(amount) — memo table and recursion stack

2. Dynamic Programming (Bottom-Up)

Intuition

Build a dp array where dp[i] = fewest coins needed to make amount i. Start with dp[0] = 0 (zero coins for zero amount), and initialize everything else to infinity.

For each amount from 1 to amount, try every coin: if dp[i - coin] + 1 < dp[i], update. This is the classic unbounded knapsack pattern — you can use each coin as many times as needed.

Algorithm

1. Initialize dp = [inf] * (amount + 1), dp[0] = 0.
2. For each i from 1 to amount:
   • For each coin in coins:
     • If coin <= i and dp[i - coin] + 1 < dp[i]: update dp[i].
3. Return dp[amount] if not infinity, else -1.

Solution

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], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1


print(coinChange([1, 5, 11], 15))  # 3  (5+5+5)
print(coinChange([2], 3))          # -1
print(coinChange([1, 2, 5], 11))  # 3  (5+5+1)
print(coinChange([1], 0))          # 0
print(coinChange([1], 1))          # 1
print(coinChange([186, 419, 83, 408], 6249))  # 20

Complexity

• Time: O(amount * len(coins)) — nested loop
• Space: O(amount) — DP array

Common Pitfalls

Initializing dp to 0 instead of infinity. You want to find the minimum, so uncomputed states should start at infinity to avoid false minimums. Only dp[0] = 0 is the true base case.

Not checking if the answer is reachable. If dp[amount] is still infinity after filling, no valid combination exists — return -1.

Confusing this with 0/1 knapsack. In Coin Change, you can use each coin unlimited times (unbounded). In 0/1 knapsack, each item is used at most once. The bottom-up loop order here (iterating amounts in the outer loop) supports unbounded usage.