Coin Change

How it works

Think of each amount as a node in a graph.

• From a current amount x, you can go to x + coin for every coin.
• Each edge represents using one coin.
• We want the minimum number of coins, which means the shortest path from 0 to amount.

This makes the problem a shortest path in an unweighted graph, so Breadth First Search (BFS) is a natural fit.

BFS explores level by level:

• Level 1 → amounts reachable using 1 coin
• Level 2 → amounts reachable using 2 coins
• First time we reach amount, we've used the minimum coins.

Steps

1. If amount == 0, return 0
2. Initialize a queue with 0 (starting amount)
3. Use a seen array to avoid revisiting amounts
4. Set steps = 0
5. While the queue is not empty:
   • Increment steps (represents number of coins used)
   • For each element in the current level:
     • Try adding every coin
     • If current + coin == amount, return steps
     • If within bounds and unseen, mark seen and push into queue
6. If BFS finishes without reaching amount, return -1

Complexity

• Time complexity: O(n * t)
• Space complexity: O(t)

Where n is the length of the array coins and t is the given amount.

Things to watch for

Using Greedy Instead of DP

A common mistake is assuming a greedy approach (always picking the largest coin) works. For coins = [1, 3, 4] and amount = 6, greedy picks [4, 1, 1] (3 coins), but the optimal is [3, 3] (2 coins). The problem requires exploring all combinations.

Incorrect Handling of Impossible Cases

Forgetting to return -1 when the amount cannot be formed. Using 0 or leaving the result as infinity/large value causes wrong answers.

Integer Overflow When Adding 1 to Infinity

When using INT_MAX or Integer.MAX_VALUE as the "impossible" sentinel, adding 1 causes overflow. Use amount + 1 as the sentinel instead, since you can never need more than amount coins (when using coin value 1).

from typing import List
from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0

        q = deque([0])
        seen = [False] * (amount + 1)
        seen[0] = True
        res = 0

        while q:
            res += 1
            for _ in range(len(q)):
                cur = q.popleft()
                for coin in coins:
                    nxt = cur + coin
                    if nxt == amount:
                        return res
                    if nxt > amount or seen[nxt]:
                        continue
                    seen[nxt] = True
                    q.append(nxt)

        return -1

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) return 0;

        queue<int> q;
        q.push(0);
        vector<bool> seen(amount + 1, false);
        seen[0] = true;
        int res = 0;

        while (!q.empty()) {
            res++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int cur = q.front();
                q.pop();
                for (int coin : coins) {
                    int nxt = cur + coin;
                    if (nxt == amount) return res;
                    if (nxt > amount || seen[nxt]) continue;
                    seen[nxt] = true;
                    q.push(nxt);
                }
            }
        }

        return -1;
    }
};