← Greedy · guided lesson
Greedy Algorithms
the story
The greedy method
Every tool here exists because something was too slow or broke without it. Here is what.
Greedy rules were in use before anyone could say when they work. Kruskal's 1956 minimum spanning tree adds the cheapest safe edge, again and again. Rado (1957), Gale (1968) and Edmonds (1971) found the clean answer for one big family of problems: "take the best remaining item that still fits" is optimal for every choice of weights exactly when the structure is a matroid. Edmonds' paper "Matroids and the greedy algorithm" is the classic reference. For everyday interview problems, you prove each greedy rule by hand instead: exchange argument or stays ahead.
the problem it solved
Knowing in advance when "always take the best remaining item" is guaranteed to be optimal, instead of hoping.
why it matters: without it
Many scheduling and selection problems would need DP or brute force: O(n²) or worse, where one sort and one pass would do.
sources: Kruskal — On the shortest spanning subtree of a graph and the traveling salesman problem (Proc. AMS, 1956) ↗ · Rado — Note on Independence Functions (Proc. London Math. Soc., 1957) ↗ · Gale — Optimal assignments in an ordered set: An application of matroid theory (J. Combinatorial Theory, 1968) ↗ · Edmonds — Matroids and the greedy algorithm (Mathematical Programming, 1971) ↗
also in this chapter: Proving greedy: exchange argument & stays ahead · Furthest reach (BFS on a line without a queue) · Change-making: where greedy breaks
the idea
The idea in 30 seconds
A greedy algorithm builds the answer one step at a time. Each step takes the choice that looks best right now, and never undoes it.
It is usually one sort plus one pass: fast and short. But it is only correct when you can argue that the local best choice never blocks the best overall answer.
So greedy is two skills: spotting the safe choice, and proving it safe (or breaking it with a tiny counter-example and switching to DP).
picture this
Your download manager has five files queued on one connection. To make the average wait smallest, start the smallest file first. If a big file ever runs just before a smaller one, swap them: the small one finishes earlier, and the pair still ends at the same moment. Every such swap helps, so shortest-first wins. That swap is the exchange argument, the proof behind most greedy answers.
watch it
When greedy fails: biggest coin first
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
When greedy fails: biggest coin first
Try coins 1, 3, 4 with amount 6. Then try 1, 2, 5, 10, where greedy happens to be right.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Jump Game: one number of state
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Jump Game: one number of state
Only the furthest reachable index matters. If `i` ever passes it, you're stuck.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 11
Read it once. Say it out loud once. Bas.
Greedy choice property: some best answer starts with the greedy choice. Optimal substructure: after that choice, what's left is a smaller copy of the same problem. You need both.
key idea 2 of 11
Read it once. Say it out loud once. Bas.
Exchange argument: take any best answer. Swap its first choice that differs from greedy's for the greedy one. Show it's still valid and no worse. Repeat, and the best answer becomes the greedy answer.
key idea 3 of 11
Read it once. Say it out loud once. Bas.
Greedy stays ahead: show that after every step, greedy's state is at least as good as anyone else's. Jump Game's reach is never behind any other sequence of jumps.
key idea 4 of 11
Read it once. Say it out loud once. Bas.
Greedy can be wrong. Coins {1, 3, 4}, amount 6: biggest-first pays 4+1+1 (3 coins), but 3+3 is 2. When no proof works, or a tiny input breaks it, use DP.
key idea 5 of 11
Read it once. Say it out loud once. Bas.
Furthest reach: in Jump Game the reachable indices always form a prefix [0..reach], so one integer replaces a whole search. Jump Game II counts BFS levels with two integers.
key idea 6 of 11
Read it once. Say it out loud once. Bas.
Restart past a failure: in Gas Station, if the tank goes negative at i, no start in [start..i] can work, so jump straight to i + 1. One pass.
key idea 7 of 11
Read it once. Say it out loud once. Bas.
Keep a range of possibilities: when a choice is unknown (a * in LC 678), track the smallest and largest possible state instead of trying every choice.
key idea 8 of 11
Read it once. Say it out loud once. Bas.
Filter, then combine: in Merge Triplets, anything that overshoots the target is useless forever, and everything else is harmless to merge.
key idea 9 of 11
Read it once. Say it out loud once. Bas.
Two passes for two-sided rules: Candy satisfies "more than the left neighbour" in one pass and "more than the right" in another, then takes the max.
key idea 10 of 11
Read it once. Say it out loud once. Bas.
Forced choices: in Hand of Straights the smallest card must start a group, because nothing smaller is left to come before it.
key idea 11 of 11
Read it once. Say it out loud once. Bas.
Typical cost: O(n) for the pass, O(n log n) if you sort first. Intervals (next chapter) are greedy's biggest family.
spot the pattern
When you see this, think this
"Can you reach the end?" / "fewest jumps"
Furthest reach; BFS levels without a queue
Circular route with a running balance
Gas Station: restart after any prefix that goes negative
Constraints from both neighbours (left and right)
Two passes, one per direction (Candy)
"Split into as many parts as possible" with a last-occurrence rule
Partition Labels: stretch the end to the last index
+5 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Using greedy without a proof. Always try 2–3 tiny counter-examples first (coins {1, 3, 4}, amount 6).
- Jump Game II: looping to
i < ninstead ofi < n - 1. That adds one extra jump when you land exactly on the end.
quick check
One question. No pressure.
Coins {1, 3, 4}, amount 6. What does biggest-coin-first return, and what is optimal?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Jump Game
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Which two properties make a greedy algorithm correct?
Question 1: Which two properties make a greedy algorithm correct?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.