Greedy (exchange argument)

O(n log n)

Greedy change-making takes the largest coin that still fits the remaining amount, one coin at a time, and never revisits that choice. It gives the true minimum only when the denominations are canonical, which is why the exchange argument matters.

Signals

fewest coins or pieces to make an amountlargest that still fits, taken greedilymake change with denominationsprove optimality with an exchange argument

Template

function minCoinsGreedy(coins, amount) {
    const sorted = [...coins].sort((a, b) => b - a);
    const used = [];
    for (const coin of sorted) {
        while (amount >= coin) {
            amount -= coin;
            used.push(coin);
        }
    }
    return amount === 0 ? used : null;
}

Looks similar, isn't

Dynamic programming: Greedy grabs the largest coin that fits and never revisits that choice, which only gives the true minimum when the denominations are canonical, like standard currency. On a non-canonical coin set greedy can overshoot, and dynamic programming, tabulating the minimum coins for every amount up to the target, is the reliable fix.

denominations up to ~20 kinds sorted once, then one payout pass -> O(n log n): sorting the coins dominates, the payout walk itself is O(amount).

Learn this pattern