Overview
The greedy paradigm builds a solution by repeatedly taking the choice that looks best right now. For coin change it means: at each step take the largest coin that still fits into the remaining amount, then repeat.
Greedy is fast and simple, but its answer is only optimal for 'canonical' coin systems (like standard currencies). For other systems it is provably sub-optimal — with coins {1, 3, 4} making 6, greedy picks 4+1+1 (three coins) while the true optimum is 3+3 (two coins).
How Greedy (Coin Change) works
- Sort the denominations in descending order so the largest comes first.
- Take as many of the current largest coin as fit into the remaining amount.
- Subtract the coins taken from the remaining amount and move to the next smaller coin.
- Stop when the remaining amount reaches zero, or report failure if no coin fits.
When to use it
- Making change with canonical systems (e.g. 1, 5, 10, 25) where greedy is provably optimal.
- Problems with the greedy-choice property and optimal substructure (Huffman coding, interval scheduling, MST).
- Switch to dynamic programming for arbitrary coin systems, where greedy can give the wrong count.
Complexity analysis
Greedy coin change sorts the denominations in O(n log n) and then does a single linear sweep, so it runs in O(n log n) time (O(n) if coins arrive sorted) and O(1) extra space. Its cost is the risk of a non-optimal answer on non-canonical systems — a classic reminder that speed does not imply correctness.
Frequently asked questions
When does greedy coin change fail?
On non-canonical systems. With coins {1, 3, 4} making 6, greedy takes 4 then 1+1 for three coins, but 3+3 uses only two. Whenever a larger coin blocks a better combination of smaller ones, greedy is sub-optimal.
How do I guarantee the minimum number of coins?
Use dynamic programming: dp[amount] = 1 + min over coins c of dp[amount − c]. It runs in O(amount × n) time and is optimal for any coin system, unlike greedy.