Greedy¶
Also known as: Locally Optimal Choice, Exchange Argument
Take the best-looking option right now and never reconsider. It's the simplest strategy imaginable, and it's usually wrong — the entire skill is recognising the rare problems where it's provably right.
Before you start¶
- Comfortable with sorting and basic comparisons in your language.
What 'solved properly' looks like
Target: Usually O(n log n) with a sort, sometimes O(n). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
At each step, you make the choice that looks best right now, and you never revisit it. There is no table, no recursion, no backtracking — just a decision rule that happens to be correct for the whole problem. The difficulty is never in the implementation; it's in convincing yourself (and an interviewer) that the greedy choice never backfires.
Why it matters: Greedy is the simplest strategy to write and the hardest to prove correct. Most optimisation problems that aren't DP are greedy, and the exchange argument (if an optimal solution differs from yours, you can swap one element without making it worse) is worth understanding even if you never write one formally.
When to reach for it¶
Reach for it when you need the "minimum number of X", interval scheduling, jump games, assignment problems, or when there's a natural ordering that makes one choice obviously safe — like always picking the smallest cookie that satisfies a child.
When not to use it
Greedy is only valid when the greedy-choice property holds — that a locally best move can never hurt you later. If you can't argue that, you probably need DP. The dangerous part is that greedy passes small test cases far more often than it's actually correct, so "it worked on the examples" is not evidence.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Assign Cookies | LeetCode | Easy | 15 mins | teaching |
| 2 | Jump Game | LeetCode | Medium | 20 mins | teaching |
| 3 | Jump Game II | LeetCode | Medium | 25 mins | consolidation |
| 4 | Partition Labels | LeetCode | Medium | 20 mins | consolidation |
| 5 | Gas Station | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Gas Station cleanly in one sitting — handling the total-sum check and the single-pass start-point logic — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.