Introduction to Greedy Algorithms
Learn the Greedy technique: Making locally optimal choices to solve global problems efficiently.
Examples
10 + 5 + 1 + 1 + 1. Greedy is optimal for this coin system.
Greedy takes 4 + 1 + 1. The true minimum is 2, from 3 + 3 — greedy is wrong here.
Greedy takes the 5 and cannot finish the 4 left over, although 3 + 3 + 3 works.
What is a Greedy Algorithm?
A Greedy Algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
It follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
The Motivation: Coin Change
Imagine you are a cashier who has to give change for 18 using the fewest coins possible.
The coins available are 10, 5 and 1.
How do you decide which ones to hand over?
Attempt 1: Brute Force
One way is to try every possible combination of coins that adds up to 18 and keep the one with the fewest coins:
- 1 + 1 + 1 + … (18 coins)
- 10 + 1 + 1 + … (9 coins)
- 5 + 5 + 5 + 1 + 1 + 1 (6 coins)
- 10 + 5 + 1 + 1 + 1 (5 coins)
It always finds the true minimum, but the number of combinations grows exponentially with the amount and the number of coin values. The figure below can run it: switch it to Every combination and watch how many it has to check.
When to use Greedy?
Pattern Recognition Triggers:
- Greedy Choice Property: You can choose the best option right NOW and it never negatively impacts future choices.
- Optimal Substructure: The optimal solution to the problem contains optimal solutions to sub-problems.
The Intuition: Pick the Biggest Coin!
Instead of trying everything, use a simple rule:
- We want the remaining amount to shrink as fast as possible.
- The
10coin shrinks it the fastest. - So take as many
10s as fit, then as many5s, then1s.
This is greedy: at every step it grabs the biggest value available and never reconsiders.
Interactive Walkthrough (Optimal)
ONE COLUMN PER COIN, LARGEST FIRST · THE ROW BELOW IS HOW MANY OF IT ARE USED
SORT LARGEST FIRST
0
1
2
coin
used
left to make
18
coins used
0
greedy vs the minimum
greedy
5
minimum
5
Greedy found the minimum
Sort the coins largest first: 10, 5, 1. 18 is left to make
Next
Next is the 10. 18 is left
coins
Target
Legend & Complexity
How many of the coin being considered are used
The coin being considered
A dash: not reached yet
Greedy
O(k log k)
Space
O(1)
Every combination
exponential
One table, filled two ways. Each column is a coin value, largest first; the row beneath counts how many of it are used.
- Greedy runs the code below: one decision per coin, never revisited.
- Every combination runs the exhaustive search and finds the true minimum.
Both answers stay beside the figure whichever mode is showing. Try Fails: greedy says 3, the minimum is 2.
Dry Run Table
Coins [10, 5, 1], amount 18:
| Coin | Fits? | Take | Paid | Left | Coins used |
|---|---|---|---|---|---|
| 10 | 10 ≤ 18 | 18 // 10 = 1 | 10 | 8 | 1 |
| 5 | 5 ≤ 8 | 8 // 5 = 1 | 5 | 3 | 2 |
| 1 | 1 ≤ 3 | 3 // 1 = 3 | 3 | 0 | 5 |
Nothing is left after three decisions, so the answer is 5 coins — and for this coin system that is the minimum.
Solution Template
The greedy method in six languages — the lines light up as the figure above steps in Greedy mode.
Introduction to Greedy Algorithms Code
1var greedyCoins = function(coins, amount) {2 coins.sort((a, b) => b - a);3 let count = 0;4 for (const coin of coins) {5 if (coin > amount) {6 continue;7 }8 const take = Math.floor(amount / coin);9 amount -= take * coin;10 count += take;11 }12 return amount === 0 ? count : -1;13};
Edge Cases & Warning
Always check if Greedy works:
Non-canonical coins break it. With [4, 3, 1] and 6, greedy answers 3 coins (4 + 1 + 1) when 2 (3 + 3) exist. Switch the figure to Every combination to see the true minimum.
Greedy can give up when an answer exists. With [5, 3] and 9, greedy takes the 5 and is stranded at 4. It returns -1, yet 3 + 3 + 3 works.
Sort first. The whole method depends on meeting the largest coin first. Unsorted input makes it take small coins while larger ones would still fit.
Summary
Recap: Greedy is fast and intuitive but doesn't always work (like the 4,3,1 coin example). Always verify the "Greedy Choice Property" holds before using it.