Coin change: greedy vs optimal

easy

With coins 1, 3, 4 and a target of 6, greedy takes three coins where two suffice. Both answers are shown side by side, which is the fastest way to internalise when greedy is unsafe.

Best O(n log n) greedyWorst O(amount × coins) DPSpace O(amount) for the DP

Loading the coin change: greedy vs optimal engine…

0 / 83 algorithms

Saved in this browser - no sign-up, nothing sent anywhere.

How coin change: greedy vs optimal works

Always take the largest coin that still fits, and repeat until the amount is gone. With US denominations 1, 5, 10, 25 this is genuinely optimal: for 6 cents greedy takes 5 + 1, two coins, exactly matching the dynamic-programming answer. Such systems are called canonical, and real currencies are deliberately designed this way - it is why a cashier can make change without solving an optimisation problem.

Change the coins to 1, 3, 4 and ask for 6, and the same rule fails. Greedy grabs the 4, leaving 2 - an amount only 1s can finish - and ends with 4 + 1 + 1, three coins, where 3 + 3 needs two. The greedy choice property is what broke: the locally best first coin, the 4, appears in no optimal answer at all.

Dynamic programming has no such blind spot. dp[a] records the fewest coins that make amount a; every coin is considered at every amount, so no first choice can trap it, at the price of O(amount × coins) work instead of a sort and a sweep. The module runs both and shows the coin counts side by side - canonicity is not something you can eyeball, so on an unfamiliar coin system the table is the safe default.

Step by step

Choose the broken system: coins 1, 3, 4, target 6. Sort descending to 4, 3, 1 and always take the largest coin that fits.
The 4 fits into 6. Take it, leaving 2 - and a second 4 no longer fits.
Try the 3: it does not fit into 2 either. Greedy falls through to the 1.
Take a 1, then another. The amount reaches 0 and greedy stops at three coins: 4 + 1 + 1.
The DP fills dp[0..6]. dp[3] is one coin, so dp[6] = dp[3] + 1 = 2, reached as 3 + 3.
Side by side: greedy three coins, optimal two. Switch to 1, 5, 10, 25 and greedy's 5 + 1 matches the DP exactly.

Complexity

Best case time	O(n log n) greedy
Worst case time	O(amount × coins) DP
Space	O(amount) for the DP

Greedy is correct only for canonical coin systems.

Reference implementation

Python

def greedy_change(coins, amount):
    """Always take the largest coin that fits."""
    coins = sorted(coins, reverse=True)
    used = []
    for c in coins:
        while amount >= c:
            used.append(c)
            amount -= c
    return used if amount == 0 else None


def optimal_change(coins, amount):
    """Dynamic programming - always correct."""
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] < INF else None

JavaScript

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

function optimalChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  return dp[amount] === Infinity ? null : dp[amount];
}

Worth noticing

Greedy is correct only for canonical systems

With 1, 3, 4 and a target of 6, greedy takes 4 + 1 + 1 = three coins. The optimum is 3 + 3 = two. Real currencies are designed so greedy works; arbitrary coin sets are not.

Why greedy fails here

Taking the biggest coin can leave a remainder that only smaller coins fit badly. The greedy choice property - that a locally optimal pick is part of some global optimum - simply does not hold for every coin system.

Dynamic programming has no such restriction

The DP considers every coin at every amount, so it cannot be trapped by a bad first choice. It costs O(amount × coins) instead of O(coins), which is the price of correctness.

Common pitfalls

Trusting greedy on arbitrary coin sets. It is provably right for canonical systems like 1, 5, 10, 25 and demonstrably wrong for 1, 3, 4.
Concluding greedy works because it matched the DP on a few amounts. Correctness must hold for every amount, and the first failure can sit well past the values you tried.
Believing failure needs exotic coins. 1, 7, 10 looks harmless, yet for 15 greedy spends six coins - a 10 and five 1s - where 7 + 7 + 1 takes three.
Returning the greedy count without checking the amount actually reached zero. Without a 1 in the coin set the loop can stall - the implementations here return None or null for a reason.
Reaching for greedy on LeetCode 322. Its test cases use arbitrary coin systems precisely to sink the largest-coin-first idea; the expected solution is the DP.

Where it is used

Making change at a till - real currencies are canonical, so the two-second greedy is safe.
LeetCode 322, coin change - the interview trap where greedy fails and the DP is the expected answer.
Vending machines and payment terminals dispensing change in fixed denominations.
The standard classroom example for testing the greedy choice property before trusting any greedy algorithm.

Frequently asked questions

What is the time and space complexity of greedy coin change?

The greedy pass is O(n log n) at best - sorting the coins dominates, and the sweep after it is linear in the coins taken. The always-correct DP shown alongside costs O(amount × coins) time and O(amount) space for its table. The gap between a sort and a table is the price of working on every coin system.

Why does greedy fail for coins 1, 3, 4?

Taking the 4 from 6 leaves 2, and no combination of 3s and 4s makes 2, so greedy pads with two 1s for three coins total. Starting with a 3 instead leaves 3, finished by one more 3. The biggest first coin created the worst possible remainder.

What makes a coin system canonical?

One where largest-coin-first matches the true minimum for every amount. US coins 1, 5, 10, 25 qualify; 1, 3, 4 and 1, 7, 10 do not. There is no eyeball test - canonicity is verified by checking greedy against the DP across amounts, which is exactly what this visualizer does.

Should I use greedy or dynamic programming for coin change?

Ask what the coin system is. For a fixed real currency, greedy is fine and fast. For arbitrary or unknown denominations - LeetCode 322 territory - use the DP: it costs O(amount × coins) but cannot be trapped by a bad first choice. Explaining why greedy fails is usually worth as much as the code.

Where to go next

Coin change (DP)

medium

One subproblem per amount, and no first choice can trap it.

Fractional knapsack

medium

Densest first, and split the last item.

Activity selection

easy

Earliest finish time - and two plausible rules that fail.

How coin change: greedy vs optimal works

Step by step

Choose the broken system: coins 1, 3, 4, target 6. Sort descending to 4, 3, 1 and always take the largest coin that fits.

The 4 fits into 6. Take it, leaving 2 - and a second 4 no longer fits.

Try the 3: it does not fit into 2 either. Greedy falls through to the 1.

Take a 1, then another. The amount reaches 0 and greedy stops at three coins: 4 + 1 + 1.

The DP fills dp[0..6]. dp[3] is one coin, so dp[6] = dp[3] + 1 = 2, reached as 3 + 3.

Side by side: greedy three coins, optimal two. Switch to 1, 5, 10, 25 and greedy's 5 + 1 matches the DP exactly.

Best case time

O(n log n) greedy

Worst case time

O(amount × coins) DP

Space

O(amount) for the DP

Reference implementation

Python

def greedy_change(coins, amount):
    """Always take the largest coin that fits."""
    coins = sorted(coins, reverse=True)
    used = []
    for c in coins:
        while amount >= c:
            used.append(c)
            amount -= c
    return used if amount == 0 else None


def optimal_change(coins, amount):
    """Dynamic programming - always correct."""
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] < INF else None

JavaScript

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

function optimalChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
  return dp[amount] === Infinity ? null : dp[amount];
}

Worth noticing

Greedy is correct only for canonical systems

With 1, 3, 4 and a target of 6, greedy takes 4 + 1 + 1 = three coins. The optimum is 3 + 3 = two. Real currencies are designed so greedy works; arbitrary coin sets are not.

Why greedy fails here

Dynamic programming has no such restriction

The DP considers every coin at every amount, so it cannot be trapped by a bad first choice. It costs O(amount × coins) instead of O(coins), which is the price of correctness.

Common pitfalls

Trusting greedy on arbitrary coin sets. It is provably right for canonical systems like 1, 5, 10, 25 and demonstrably wrong for 1, 3, 4.

Concluding greedy works because it matched the DP on a few amounts. Correctness must hold for every amount, and the first failure can sit well past the values you tried.

Believing failure needs exotic coins. 1, 7, 10 looks harmless, yet for 15 greedy spends six coins - a 10 and five 1s - where 7 + 7 + 1 takes three.

Returning the greedy count without checking the amount actually reached zero. Without a 1 in the coin set the loop can stall - the implementations here return None or null for a reason.

Reaching for greedy on LeetCode 322. Its test cases use arbitrary coin systems precisely to sink the largest-coin-first idea; the expected solution is the DP.

Where it is used

Making change at a till - real currencies are canonical, so the two-second greedy is safe.

LeetCode 322, coin change - the interview trap where greedy fails and the DP is the expected answer.

Vending machines and payment terminals dispensing change in fixed denominations.

The standard classroom example for testing the greedy choice property before trusting any greedy algorithm.