juniorGreedy Algorithms
Coin Change: When does Greedy work?
Updated Apr 28, 2026
Short answer
Greedy works for canonical systems (like USD) but fails for general denominations.
Deep explanation
Greedy algorithms are defined by the 'Greedy Choice Property'. Greedy works for canonical systems (like USD) but fails for general denominations. Unlike backtracking, once a choice is made, it is never reconsidered.
Real-world example
Giving change with the fewest coins in a standard currency.
Common mistakes
- Assuming greedy works for all optimization problems without proof.
Follow-up questions
- Is Greedy always faster than DP?