4.23.8 — Coin Change

LeetCode 322 · Medium · ★ Blind 75

The problem

Given coin denominations and an amount, return the fewest coins that make the amount, or -1 if it cannot be made. You have unlimited coins of each type.

coins = [1,2,5], amount = 11   →  3     (5 + 5 + 1)
coins = [2],     amount = 3    →  -1

Amount up to 10,000.

Restating the Problem: You are a cashier tasked with returning a specific amount of change, but you want to give the customer the fewest physical coins possible. You have a bottomless drawer of each coin denomination provided.

Constraints to Note:

• The amount can be up to 10^4.
• You can have up to 12 different coin denominations.
• A coin's value can be up to 2^{31} - 1.
• Because of the amount limit, an O(Amount \times Coins) algorithm will take at most 120,000 operations, which is incredibly fast.

The Brute Force Approach

The brute force method is to explore every possible coin choice. At each step, if we need to make amount A, we try subtracting each coin denomination C. Then we recursively find the fewest coins to make A - C. Since we can reuse coins, each recursive step branches into K paths (where K is the number of coin types). The depth of the recursion can be up to Amount (if we just use 1-cent coins). This yields a time complexity of O(K^{Amount}). For amount=11 and 3 coins, that's 3^{11} \approx 177,000. For amount=10,000, it's literally impossible to compute in a human lifetime. We must memoize or use DP.

Why greedy fails

This is the reference example for the DP-versus-greedy question from 4.22, so it is worth having the counterexample ready.

Greedy rule: always take the largest coin that fits.

Counterexample: coins = [1, 3, 4], amount = 6. Greedy takes 4, then 1, then 1 — three coins. The right answer is 3 + 3 — two coins.

Real currencies are deliberately designed so that greedy works, which is exactly why the intuition is so strong and so wrong. When the denominations are arbitrary, greedy is not safe, and one counterexample settles it.

The pattern

Let dp[a] be the fewest coins making amount a.

To make amount a, the last coin you used was some coin c. Before that you had made a − c, using dp[a - c] coins. So:

dp[a] = 1 + \min_{c \,\in\, \text{coins},\ c \le a} dp[a - c]

Read aloud: the cheapest way to make a is one coin, plus the cheapest way to make whatever was left after that coin. Try every coin as the last one and keep the best.

dp[0] = 0 — making zero needs no coins. That is the base case and everything builds from it.

The solution

Python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = amount + 1                     # bigger than any real answer
        dp = [INF] * (amount + 1)
        dp[0] = 0

        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    dp[a] = min(dp[a], 1 + dp[a - c])

        return dp[amount] if dp[amount] != INF else -1

TypeScript

function coinChange(coins: number[], amount: number): number {
  const INF = amount + 1;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a) dp[a] = Math.min(dp[a], 1 + dp[a - c]);
    }
  }

  return dp[amount] === INF ? -1 : dp[amount];
}

INF = amount + 1 rather than infinity. The most coins any reachable amount could need is amount (all 1s), so amount + 1 is unreachable and marks "impossible" without needing floats. It also keeps 1 + dp[...] safe from overflow concerns in typed languages.

The loop order. dp[a] reads dp[a - c], which is always smaller, so the outer loop counts upwards and every cell it needs is already filled.

Coins may be reused freely, and the code allows that automatically: dp[a - c] may itself have used coin c. Compare 4.23.12 Partition Equal Subset Sum, where each item is used once and the loop must run downwards to prevent reuse. That loop direction is the entire difference between the two problems, and it is the trap named in 4.22.

Trace

coins = [1, 2, 5], amount = 6

a	best option	dp[a]
1	1 + dp[0]	1
2	1 + dp[0] via coin 2	1
3	1 + dp[1] via coin 2	2
4	1 + dp[2] via coin 2	2
5	1 + dp[0] via coin 5	1
6	1 + dp[5] via coin 1	2

Two coins for 6: 5 + 1 ✓.

The top-down version

from functools import lru_cache

def coinChange(self, coins, amount):
    @lru_cache(None)
    def fewest(a: int) -> float:
        if a == 0: return 0
        if a < 0: return float('inf')
        return min((1 + fewest(a - c) for c in coins), default=float('inf'))

    result = fewest(amount)
    return -1 if result == float('inf') else result

Easier to derive, because it is just the recurrence written down. It costs stack depth and hash lookups, and it computes only the amounts actually reachable — which is a genuine advantage when the coins are large and most amounts are unreachable.

Derive with this, ship the table.

Complexity

O(\text{amount} \times \text{number of coins}) time, O(\text{amount}) space.

Time Complexity Derivation: We have an outer loop running from 1 to amount (which is O(\text{amount}) iterations). Inside that, we loop through all C coin denominations (which is O(\text{coins}) iterations). The operation inside the inner loop is an O(1) constant-time lookup and addition. Multiplying these gives O(\text{amount} \times \text{coins}).

Space Complexity Derivation: We create a 1D array dp of size amount + 1 to store the fewest coins for every amount up to the target. This directly takes O(\text{amount}) memory. We don't use any other data structures.

This is pseudo-polynomial, and the distinction is worth knowing. The runtime is polynomial in the value of the amount, not in the number of bits used to write it. Doubling the number of digits in the amount multiplies the work by ten. Coin Change is a cousin of the knapsack problem for exactly this reason, and 4.29 explains why that matters.

Where this goes next

• Coin Change II — count the number of combinations rather than the fewest coins. The loop order flips: coins outside, amounts inside, or you count permutations by accident. That is 4.24.4 and it is one of the most instructive loop-order lessons in the book.
• Combination Sum IV — counts permutations, so the loops go the other way round. Compare the two and the difference becomes obvious.
• Perfect Squares — Coin Change where the coins are 1, 4, 9, 16 and so on.
• Minimum Cost For Tickets — the same shape with three "coins" of different durations.

What the interviewer will push on

"Why not greedy?" [1, 3, 4] and amount 6. Have it ready before they ask.

"What does dp[a] mean?" The fewest coins making exactly a.

"Why dp[0] = 0?" Zero needs no coins, and every other value is built from it.

"How do you mark impossible?" A sentinel larger than any real answer, then convert to -1 at the end.

"Why does the loop go upwards, and when would it go down?" Upwards allows reuse. Downwards prevents it, which is what 0/1 knapsack needs.

"What is the complexity, and is that polynomial?" O(\text{amount} \times \text{coins}), and it is pseudo-polynomial — polynomial in the value, not in the input size.

"How would you return the actual coins?" Store, for each amount, which coin gave the best answer, then walk backwards from amount. Reconstruction needs the table, which is the one thing the O(1)-space tricks give up.

One thing to volunteer: open with the greedy counterexample. It settles the technique choice in ten seconds and shows you tested your first instinct instead of trusting it.

Next: 4.23.9 Maximum Product Subarray — where you have to carry two values because a negative can turn the worst into the best.