Algorithms from zero
What is a greedy algorithm? Local choice vs DP
You need to make 30 cents in change with US coins. Almost without thinking you reach for a quarter, then a nickel—done, two coins. You did not draw a decision tree or try every combination. You grabbed the biggest coin that fit, then the next biggest, and never looked back. That instinct has a name: a greedy algorithm. It is the simplest, fastest way to build a solution—and sometimes it is exactly wrong. Last unit, dynamic programming carefully explored every combination of subproblem choices. Greedy refuses to do that. It commits to one local choice at each step and moves on. The whole skill is knowing when that shortcut is safe.
After this lesson you can define a greedy algorithm: it builds a solution by repeatedly taking the locally-best choice and never reconsidering it. You can name the two conditions that make greedy correct—the greedy-choice property (a globally optimal solution can always start with the locally-best choice) and optimal substructure (an optimal solution contains optimal solutions to its subproblems). You can contrast greedy with dynamic programming: DP explores all combinations of subproblem choices and keeps the best, while greedy commits to one choice and never backtracks—so greedy is faster but only sometimes correct. You can give an example where greedy works (making change with the canonical US system 25) and a concrete counterexample where it fails (4 for amount 6: greedy gives 4+1+1 = 3 coins, but the optimum is 3+3 = 2 coins). You understand why this means a greedy algorithm must be proven correct, not just assumed—the subject of the next lesson. And you can state the typical cost: when greedy is valid it is usually O(n log n), dominated by an initial sort.
What is a greedy algorithm?
A greedy algorithm builds a solution one piece at a time. At each step it makes the choice that looks best right now—the locally optimal move—and then it never reconsiders that choice. No backtracking, no trying the road not taken. It marches straight from start to finish, grabbing the best-looking option at every fork.
That is the entire idea, and it is why greedy is fast and simple. There is no recursion tree to explore, no table of subproblems to fill. You sort or scan the input, take the best choice, repeat.
Greedy vs dynamic programming
Last unit’s dynamic programming and greedy attack the same kind of problem—building an optimal solution from subproblem choices—but in opposite spirits:
- Dynamic programming explores all the combinations of subproblem choices, computes the best of each, and keeps the overall best. It hedges: it does not commit until it has compared the alternatives.
- Greedy commits to one choice at each step—the locally best one—and never compares it against the alternatives later. It bets that the locally best choice is also part of the globally best answer.
That bet is the catch. When the bet always pays off, greedy gets the optimal answer far faster than DP. When the bet can fail, greedy returns a wrong (sub-optimal) answer while DP would still be right.
When is greedy correct? Two conditions
A greedy algorithm produces an optimal answer only when the problem has both of these properties:
- Greedy-choice property. There is always a globally optimal solution that starts with the locally-best choice. In other words, taking the greedy choice never paints you into a corner—you can always extend it to an optimum.
- Optimal substructure. After you make that first choice, what remains is a smaller version of the same problem, and an optimal solution to the whole contains an optimal solution to that remainder. (Dynamic programming needs this property too.)
If either property is missing, greedy can return a sub-optimal answer. The danger is that greedy code always runs and always returns something—it just quietly returns the wrong thing. So you must prove greedy is correct for your problem; you cannot assume it. That proof is the next lesson.
A worked counterexample: coin change
The cleanest way to feel the difference is making change with the fewest coins.
With the canonical US system 25, greedy works. To make 30, take the largest coin that fits (25), then repeat on the remaining 5 (take 5). Two coins—optimal.
Now switch to a strange coin system 4 and make 6. Greedy still grabs the largest coin that fits each time:
Coins available: {1, 3, 4} Target: 6
Greedy:
take 4 -> remaining 2 (4 is the largest coin <= 6)
take 1 -> remaining 1 (no 3 or 4 fits in 2, take 1)
take 1 -> remaining 0
result: 4 + 1 + 1 = 3 coins
Optimal:
3 + 3 = 2 coinsGreedy took the locally-best coin (the 4) and got stuck: the 4 blocked it from using two 3s. The optimum never uses a 4 at all. This is exactly a failure of the greedy-choice property—here the locally-best first move (take 4) is not part of any optimal solution. The 4 system simply does not have the property, so greedy is wrong on it. Canonical systems like 25 do have it, so greedy is right there. Same algorithm, different coins, opposite outcomes—which is exactly why correctness must be checked, not assumed.
Greedy coin change
The algorithm is short: sort the coins largest-first, then for each coin take as many as fit before moving to the next. It commits to each coin and never reconsiders.
1
function greedyChange(coins, amount) {
2
// Sort coins largest-first so we always try the biggest that fits
3
const sorted = [...coins].sort((a, b) => b - a);
4
let remaining = amount;
5
const picks = [];
6
// Walk coins from largest to smallest, never going back
7
for (const coin of sorted) {
8
// Take this coin as many times as it fits into the remainder
9
while (remaining >= coin) {
10
remaining -= coin;
11
picks.push(coin);
12
}
13
}
14
return picks; // the coins greedy chose (may not be optimal!)
15
}
- L3 Sort descending so the first coin we try at each step is the locally-best (largest) one. This sort is what makes the whole thing O(n log n).
- L7 Scan coins largest to smallest. Once we leave a coin behind we never come back to it - that is the 'never reconsider' part of greedy.
- L9 Greedy commitment: grab this coin while it still fits, before even looking at smaller coins.
- L13 Return whatever greedy picked. For {1,3,4} amount 6 this is 3 coins - sub-optimal. Greedy always returns SOMETHING; that something is only optimal when the problem has the greedy-choice property.
Running it: success on canonical coins, failure on 4
Watch the same function win on the US system and lose on 4. The code is identical; only the coin set changes.
On the US system greedy nails the optimum (63 needs 6 coins, and greedy finds 6). On 4 the very same logic returns 3 coins when 2 would do. Nothing crashed, nothing warned you—greedy just confidently returned a worse answer. That silence is precisely why a greedy solution has to be proven correct for its specific input domain.
Let us trace greedy on the failing case—coins {1, 3, 4}, amount 6—step by step, so you can see exactly where the locally-best choice leads it astray.
1
sorted = {4, 3, 1} // largest first
2
remaining = 6, picks = []
3
coin 4: while remaining >= 4 -> take 4
4
coin 3: 3 > remaining? skip
5
coin 1: while remaining >= 1 -> take 1
6
return picks
Time: O(n log n), usually dominated by a sort
A greedy algorithm makes one pass through the choices, taking O(1) (or near-O(1)) work per step, so the scan itself is O(n) for n items. But most greedy algorithms first sort the input to put the locally-best choice in front—largest coins first, shortest jobs first, earliest deadlines first—and that sort costs O(n log n). The sort dominates, so the headline cost is:
total time = O(n log n) (sort) + O(n) (greedy scan) = O(n log n)The coin-change example is even cheaper because the number of coin denominations is tiny and fixed (4 coins for the US system), so the “n” being sorted is a small constant—but the general greedy pattern is “sort, then sweep,” and that is O(n log n).
Why greedy is so much faster than DP
The speed comes entirely from not exploring alternatives. Greedy commits to one choice per step, so it does a single linear sweep. Dynamic programming, by contrast, evaluates many combinations of subproblem choices and keeps the best, so it pays for a table of states.
what it does typical time
greedy take locally-best choice, no backtrack O(n log n)
dynamic prog explore all subproblem-choice combos O(states x work) often O(n*amount)For coin change with a target amount, the DP that is always correct fills a table of size amount and is O(coins x amount). Greedy skips all of that. So when greedy is provably correct, you trade DP’s O(coins x amount) for greedy’s near-O(n log n)—a big win. The price of that win is that greedy is only correct on problems with the greedy-choice property; otherwise its speed buys you a wrong answer.
The takeaway on cost
Greedy is fast because it is shallow: one sweep, no second-guessing. Whenever you reach for greedy, the real question is never “is it fast enough” (it almost always is) but “is it correct for this problem”—which is exactly what the next lesson teaches you to prove.
What single rule defines a greedy algorithm?
How does greedy differ from dynamic programming on the same kind of problem?
Which TWO properties must a problem have for a greedy algorithm to be correct?
For coins {1, 3, 4} and amount 6, greedy returns 4 + 1 + 1 = 3 coins. What is the optimal number of coins, and why does greedy miss it?
What is the typical time complexity of a valid greedy algorithm, and why?
Greedy code for a problem WITHOUT the greedy-choice property will:
Using greedy on the canonical US system {1, 5, 10, 25}, how many coins does it take to make 30 cents (take the largest coin that fits, repeat)?
Why this works
Why learn greedy if it can be wrong? Because when it is correct, it is dramatically simpler and faster than dynamic programming—one sweep instead of a whole table—and many classic problems (activity selection, Huffman coding, minimum spanning trees, fractional knapsack, Dijkstra’s shortest paths) are built on provably-correct greedy choices. The value of greedy is not “use it everywhere”; it is “recognize the rare problems where a local choice is provably global, and exploit them for a huge speedup.” The catch—knowing which problems those are—is what makes the proof skill (next lesson) the real content of this unit.
Common mistake
Mistake: assuming greedy is correct because it “feels right” or passes a few tests. Greedy on 4 works for many amounts (1 through 5 are fine) and only fails at specific targets like 6. A handful of passing examples proves nothing—a greedy algorithm is correct only if you can prove the greedy-choice property holds for every input. Never ship a greedy solution on the strength of a few green tests; the wrong answer it returns is silent and easy to miss.
Edge cases
The same greedy can be right on one input set and wrong on another. Coin change is the textbook example: greedy is optimal on the canonical US system 25 but sub-optimal on 4. Correctness is a property of the problem instance (here, the coin denominations), not of the greedy code. So “is greedy correct for coin change?” has no single answer—you have to ask “correct for which coin system?” Whether a coin system is “canonical” (greedy-safe) is itself a question that requires checking.
More practice
The greedy checklist. Before using a greedy algorithm, ask: (1) Can I state the locally-best choice at each step? (2) Does the greedy-choice property hold—can every optimum start with that choice? (3) Does optimal substructure hold—is the remainder a smaller instance of the same problem? (4) Can I prove (2), or at least find no counterexample after trying hard? If you cannot prove it, either find a counterexample (like 4 amount 6) or fall back to dynamic programming, which is correct without the greedy-choice property. Speed is greedy’s gift; correctness is yours to earn.
Explain what a greedy algorithm is, how it differs from dynamic programming, the two conditions it needs to be correct, a case where it works and one where it fails, and its typical time complexity.
A greedy algorithm builds a solution by repeatedly taking the locally-best choice and never reconsidering it. No backtracking, no exploring alternatives—just one straight sweep, grabbing the best option at every step.
Greedy vs dynamic programming:
- DP explores all combinations of subproblem choices and keeps the best (it hedges).
- Greedy commits to one local choice per step and never compares the alternatives later (it bets).
DP is correct more broadly; greedy is faster but only correct when its bet always pays off.
Greedy is correct only with two properties:
- Greedy-choice property — a globally optimal solution can always start with the locally-best choice.
- Optimal substructure — an optimal solution contains optimal solutions to its subproblems.
If either fails, greedy still runs and still returns something—just silently sub-optimal. So greedy must be proven correct, never assumed.
The coin-change demonstration:
- Canonical US system 25: greedy is optimal (30 = 25 + 5 = 2 coins).
- System 4, amount 6: greedy gives 4 + 1 + 1 = 3 coins, but the optimum is 3 + 3 = 2 coins. The greedy-choice property fails because the locally-best first move (take 4) is in no optimal solution.
Complexity: when valid, greedy is typically O(n log n)—dominated by an initial sort, then a single O(n) sweep—far cheaper than DP’s table.
Next: lesson 02 shows how to prove a greedy algorithm correct (the exchange argument), so you can tell the 25 cases from the 4 traps before you ship.