Greedy
Intermediate · 18 min read · Problem-Solving Patterns, Greedy & Special Topics
Make the best local choice — and how to convince yourself it is safe.
A greedy algorithm makes the choice that looks best right now and never reconsiders it. When that works, it's the simplest and fastest solution there is — often one pass, O(1) memory.
Is the greedy choice safe? The exchange argument
To justify a greedy choice, argue like this:
Shape 1: track the best reach
Trying every jump sequence is exponential, and a DP over positions is O(n²). But you only need one number: the furthest index reachable so far.
Shape 2: sort, then match
Sort both. Give each child (least greedy first) the smallest cookie that satisfies them — a bigger cookie could be saved for a greedier child.
Shape 3: a running total that resets
Two facts make one pass enough:
Shape 4: two passes for two-sided rules
Each rule is easy alone. Satisfy the left neighbour rule in a left-to-right pass, then the right rule in a right-to-left pass, keeping the larger requirement:
When greedy fails
Test your greedy on two or three tiny hand-made cases before coding — if you find a counterexample, switch to DP.
Practice ladder
Interview questions
- How do you convince an interviewer that a greedy algorithm is correct?
- Why can the gas station problem skip every station between the old start and the failure point?
Further reading
Key takeaways
- Greedy = make the locally best choice and never undo it; often one pass and O(1) memory.
- Justify with an exchange argument; test small counterexamples before coding.
- Common shapes: track the best reach, sort then match, running totals that reset, two passes for two-sided rules.
- When a counterexample exists (coin change, 0/1 knapsack), use DP.