Module 33
Greedy Algorithms
Make the best local choice and never look back, but only after proving it's safe: exchange arguments, reach tracking, resets, two passes and sorting tricks.
A greedy algorithm builds the answer one step at a time, always taking the choice that looks best right now, and never reconsiders. When it works, it's usually the simplest and fastest solution. When it doesn't, it's confidently wrong, so the real skill is knowing why a greedy choice is safe.
This module teaches the two standard proofs (exchange argument and "stays ahead"), shows a case where greedy fails and DP is needed, and practises the common greedy shapes: matching sorted lists, tracking the farthest reach, resetting a start point, two-pass constraints, sorting by a clever key, and building groups from the smallest element.
Best after: Sorting and Divide & Conquer
Part 1
Learn the ideas
- 33.1When Greedy Works (and When It Doesn't)Greedy is correct when you can show some optimal answer makes the same first choice (exchange argument), or that greedy is never behind (stays ahead). Otherwise use DP.14 min
- 33.2Tracking Reach and Resetting the StartKeep the farthest point you can reach so far (Jump Game), or restart from the next position whenever a running total goes negative (Gas Station, Kadane).12 min
- 33.3Sorting Keys and Two-Pass GreedySort so the greedy choice is the next item; when constraints come from both sides, satisfy them in a left pass and a right pass.12 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Exchange argument: give each child the smallest cookie that satisfies them.
Track the farthest reachable index in one pass.
Implicit BFS levels: each range of reachable indices costs one jump.
Reset the start after any failing stretch; a non-negative total guarantees success.
Two passes for constraints from both neighbours.
Extend the current part to the last occurrence of every letter inside it.
Sorting by a clever key: place tall people first, then insert shorter ones at their index.
Pair the heaviest person with the lightest if they fit; otherwise the heaviest goes alone.
With unlimited transactions, collect every upward step.
The smallest remaining card must start a group, so build groups from it.