Decide now, never look back
In the brute-force rung you learned to consider every possibility, and in divide and conquer you learned to split a problem into independent pieces. A greedy algorithm is bolder and much lazier than either: it builds a solution one step at a time, and at each step it grabs whatever looks best right now by some simple rule, then commits to that choice forever. No branching, no backtracking, no second-guessing. Pick the nearest, the cheapest, the soonest-to-finish — whatever the rule says — add it to the answer, and move on. The whole algorithm is often a single loop with a sort in front of it, which is exactly why a working greedy method is usually the fastest tool in the box.
The contrast with the earlier rungs is the whole point. Brute force keeps every option alive and pays an exponential price for it; dynamic programming, which you will meet next, keeps a careful table of partial answers; greedy throws almost everything away and keeps only the one running answer it is building. That recklessness is its strength when it works and its downfall when it does not. So the real question of this whole rung is not how to be greedy — that part is easy — but when greedy is allowed, that is, when grabbing the locally best thing at every step actually produces a globally best solution.
A tiny example that works, and one that doesn't
Picture a thief with a knapsack that holds 10 kilograms, facing piles of gold dust, silver dust, and bronze dust. Gold is worth 6 per kilogram, silver 5, bronze 4, and there are 6 kg of each. Because dust can be split, the greedy rule is irresistible and correct: take the most valuable stuff per kilogram first. Fill 6 kg with gold (value 36), then 4 kg of the remaining capacity with silver (value 20), and stop — total 56. No other packing beats it. This is the fractional knapsack problem, and grabbing the best value-per-weight ratio at every step is provably optimal precisely because you can always top off the leftover space with a fraction of the next-best pile.
Now change one word. Instead of dust, the thief faces three indivisible bars: bar A weighs 6 kg and is worth 42, bar B weighs 5 kg worth 30, bar C weighs 5 kg worth 30. The greedy rule "highest value-per-weight first" picks bar A (ratio 7, strictly above the ratio 6 of B and C) and fills 6 of the 10 kg; bars B and C each weigh 5, so neither fits in the leftover 4 kg, and greedy walks away with 42. But the optimal answer takes B and C together — total weight 10, total value 60. Greedy lost by a mile. This is the 0/1 knapsack, and the only change was that items can no longer be split. The lesson is unsettling: the same rule, on a problem that looks almost identical, goes from perfect to badly wrong.
The two properties that make greedy correct
So what separates the two knapsacks? Greedy is provably optimal exactly when a problem has two structural properties. The first is the greedy-choice property: there exists a globally optimal solution that includes the very first choice the greedy rule makes. You never have to give up the greedy choice to reach the best answer — some best answer already agrees with it. In fractional knapsack, some optimal packing already uses as much of the highest-ratio pile as fits, so the greedy first move is safe. In 0/1 knapsack, no such guarantee holds: committing to the highest-ratio bar can lock you out of the best combination, exactly as it did above.
The second is optimal substructure: once you have locked in the greedy choice, what remains is a smaller instance of the same problem, and an optimal solution to the whole is the greedy choice plus an optimal solution to that remainder. After the thief commits 6 kg of gold, the leftover task — fill 4 kg from silver and bronze optimally — is just a smaller fractional knapsack. This is the same optimal-substructure idea that powers dynamic programming, and that overlap is not a coincidence: both paradigms attack problems whose best solutions are built from best solutions of subproblems. The difference is that greedy is allowed to commit to one subproblem without exploring the others, and the greedy-choice property is precisely the license to do so.
Both properties have to hold. Optimal substructure alone is not enough — 0/1 knapsack has optimal substructure too (which is exactly why dynamic programming solves it), yet it lacks the greedy-choice property, so greedy fails while DP succeeds. The slogan to remember: optimal substructure says the problem decomposes; the greedy-choice property says you may decompose it the greedy way, taking the locally best piece without regret. The next guides cement these properties through two general proof techniques — the exchange argument and "greedy stays ahead" — which are the actual machinery for showing the greedy-choice property in a given problem.
Local best is not global best
At the heart of every greedy failure is one gap: the difference between a local and a global optimum. A greedy rule, by construction, optimizes the choice in front of it — that choice is locally optimal. But a sequence of locally optimal choices need not add up to a globally optimal whole, because an early grab can quietly poison your later options. The 0/1 thief's first move was locally perfect (best value-per-weight) and globally catastrophic (it blocked the 60-value pairing). Greedy can only ever see one step; whether that myopia is harmless or fatal depends entirely on the problem's structure.
greedy(items):
sort items by the greedy rule # the whole "strategy" lives here
answer = empty
for x in items: # one pass, never reconsider
if x is feasible with answer:
answer = answer + x # commit forever, no backtracking
return answerNotice what this skeleton tells you about cost versus correctness. The running time is almost always dominated by the sort: a single O(n log n) sort plus a linear pass gives O(n log n) overall, which is why a correct greedy method tends to beat a divide-and-conquer or dynamic-programming approach to the same problem. But that speed is worthless if the rule is wrong — a fast wrong answer is still wrong. And remember the honest caveat from the asymptotics rung: O(n log n) describes scaling, not a verdict at every size. For tiny inputs the sort's overhead can make a clumsy quadratic method faster in wall-clock time; asymptotics tell you who wins as n grows, not who wins on ten items.
Where greedy genuinely shines
Lest all this caution make greedy sound fragile, it is worth saying loudly that when greedy works, it is often the best possible algorithm for the job — simple, fast, and exact. The rest of this rung is a tour of its triumphs: interval scheduling, where sorting jobs by finish time and grabbing each compatible one is provably optimal; Huffman coding, where repeatedly merging the two least-frequent symbols builds a provably shortest prefix code; and the celebrated minimum-spanning-tree algorithms, where Kruskal and Prim are both greedy at heart and both correct. These are not lucky accidents — each one has the greedy-choice property, and each one has a clean proof to show it.
There is even a deep, beautiful answer to "which problems is greedy correct for?" Some problems share a common abstract structure called a matroid, and there is a theorem saying that the greedy algorithm is optimal on exactly the structures that are matroids — no more, no less. This is the final guide of the rung, and it is the closest thing greedy has to a unifying law: it turns "I have a hunch greedy works here" into "this problem is a matroid, therefore greedy provably works." Not every greedy success fits the matroid mold (interval scheduling, for one, needs its own argument), but it is a striking glimpse of structure under what can otherwise feel like a pile of clever one-off tricks.
One last honest note before you climb on. Even when a problem is NOT greedy-solvable, greedy is rarely useless — it is often the foundation of an approximation. For many hard problems, a greedy rule gives an answer guaranteed to be within a fixed factor of optimal, and a much later rung makes that precise. So the spectrum is: sometimes greedy is exactly optimal (and you prove it), sometimes it is provably close (and you bound it), and sometimes it is arbitrarily bad (and you abandon it). Knowing which case you are in, and being able to prove it, is the whole skill this rung is teaching.