Greedy
Make a locally optimal choice at each step; prove (or trust) it yields a global optimum.
Interval scheduling, jump game, gas station, assign cookies, minimum platforms.
Most greedy problems require a sort or priority queue to expose the locally optimal choice, so n log n is the usual ceiling. The greedy sweep itself is linear, and extra space depends on the auxiliary structure (heap, sorted copy, or none).
Greedy makes the locally-optimal choice at each step and commits to it, never revising. It works when the problem has the 'greedy choice property' (some optimal solution starts with the locally-best move) and 'optimal substructure' (the remaining problem after the greedy move is itself the same problem). Proving both is the hard part; recognizing the situation is what interviews test.
Two common proof techniques: exchange argument (show that swapping any non-greedy choice for the greedy one doesn't make the solution worse), and staying-ahead (show the greedy solution is always at least as good as any other after k steps, by induction). You don't need to write the proof in the interview but you should articulate the intuition.
The pattern's danger is that greedy 'feels right' on many problems where it's actually wrong — coin change with arbitrary denominations is the classic trap (greedy fails for [1, 3, 4] target 6: greedy gives 4+1+1, optimal is 3+3). When in doubt, work a counterexample or fall back to DP. For interval scheduling, sorting by end time is greedy-correct; sorting by start time isn't. For jump game, the 'farthest reach so far' invariant is greedy.
Greedy requires both the greedy-choice property (some optimal solution starts with the locally-best move) and optimal substructure — when both hold, you get O(n log n) or O(n) where DP would be O(n^2) or worse.
- Assuming greedy works without proof; the classic trap is coin change with denominations like [1, 3, 4] where greedy fails.
- For interval scheduling, sorting by start time or by length — only sorting by end time gives the optimal selection.
- In jump game / gas station, computing the answer incrementally but resetting the wrong variable at the failure point.
- Trying greedy on problems requiring lookahead or revision (e.g. 'maximize profit with at most k transactions') where DP is the actual answer.
- Forgetting tie-breaking rules in sorting (two intervals ending at the same time) — usually doesn't matter, but sometimes the secondary key (e.g. shortest duration) breaks the proof.
- Interval scheduling / non-overlapping intervals: sort by end time, sweep.
- Jump game / can reach end: track farthest reachable so far.
- Gas station: single-pass cumulative balance, restart from i+1 on negative.
- Huffman coding: repeatedly merge two smallest-frequency nodes via min-heap.
- Activity selection / task scheduling: sort by deadline, schedule when possible.
// sort or scan once; at each step take the locally best move
// and prove it doesn't preclude a global optimum.
int best = 0;
for (int i = 0; i < n; i++) {
// update best given the greedy choice at i
best = Math.max(best, /* candidate */ 0);
}
return best;Problems using this pattern
2Easiest first · Blind 75 above NeetCode 150