Coin Change

The problem

Coins of given denominations (unlimited supply). Return the minimum number of coins to make amount. If impossible, return -1.

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

Brute force: recursion

function coinChangeBrute(coins: number[], amount: number): number {
  function dfs(rem: number): number {
    if (rem === 0) return 0;
    if (rem < 0) return Infinity;
    let best = Infinity;
    for (const c of coins) best = Math.min(best, 1 + dfs(rem - c));
    return best;
  }
  const ans = dfs(amount);
  return ans === Infinity ? -1 : ans;
}

Time	exponential
Space	O(amount) stack

Memoizing dfs(rem) makes it O(amount × coins).

Optimal DP (bottom-up)

dp[x] = min coins to make x.
dp[0] = 0, others Infinity.
For each amount x, try every coin c with c ≤ x:
dp[x] = min(dp[x], dp[x - c] + 1).

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

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

  return dp[amount] > amount ? -1 : dp[amount];
}

Time	O(amount ×
Space	O(amount)

Why not greedy?

coins = [1, 3, 4], amount = 6: greedy 4+1+1 = 3 coins, optimal 3+3 = 2. Greedy only works for canonical systems (like US coins) — don’t assume it.

BFS alternative

Treat amounts as graph nodes; each coin is an edge of weight 1. Shortest path from 0 to amount = min coins. Same complexity class; clean if you think in graphs.

function coinChangeBfs(coins: number[], amount: number): number {
  if (amount === 0) return 0;
  const seen = new Set<number>([0]);
  const q: number[] = [0];
  let head = 0;
  let steps = 0;

  while (head < q.length) {
    const size = q.length - head;
    steps++;
    for (let i = 0; i < size; i++) {
      const cur = q[head++];
      for (const c of coins) {
        const next = cur + c;
        if (next === amount) return steps;
        if (next < amount && !seen.has(next)) {
          seen.add(next);
          q.push(next);
        }
      }
    }
  }
  return -1;
}

Edge cases

• amount = 0 → 0
• No coins / all coins > amount → -1
• Single coin that divides amount
• Large amount — watch O(amount) memory

Common mistakes

• Greedy without proof
• Nested loop order that accidentally does 0/1 knapsack (using each coin once) — for unbounded, iterating coins outer or inner both work if you allow reuse correctly; standard is amount outer, coin inner as above
• Returning Infinity instead of -1

Interview delivery

1. Unbounded knapsack framing.
2. Reject pure greedy.
3. DP table + transition.
4. Trace [2], 3 → -1.
5. Complexity.

Related

• Climbing Stairs
• Combination Sum — combinations, not min count
• House Robber
• Word Break — similar DP reachability
• JavaScript Interview Guide

Further reading

• LeetCode 322 — Coin Change
• Unbounded knapsack