322. Coin Change

Return the fewest coins needed to make up amount, or -1 if it cannot be done. You have unlimited coins of each denomination.

Each coin is an edge from remainder r to r − c. The first time BFS reaches 0, the depth is the fewest coins.

1function coinChange(coins: number[], amount: number): number {
2  if (amount === 0) return 0;
3  const seen = new Set([amount]);
4  let queue = [amount], depth = 0;
5  while (queue.length) {
6    depth++;
7    const next: number[] = [];
8    for (const r of queue)
9      for (const c of coins) {
10        const rest = r - c;
11        if (rest === 0) return depth;
12        if (rest > 0 && !seen.has(rest)) { seen.add(rest); next.push(rest); }
13      }
14    queue = next;
15  }
16  return -1;
17}

depth = 0

queue (this level)

next level

empty

seen

Start BFS from 11.

1 / 0

Space: play/pause · ←/→: step