Overview
A greedy algorithm builds a solution step by step, always taking the option that looks best right now. When it works, it is usually the simplest and fastest solution available: one pass, sometimes after a sort. The jump game, gas station and interval scheduling problems all have elegant greedy answers.
The danger is that greedy choices can be wrong. Paying 30 with coins {1, 15, 25} greedily uses 25 + 1×5 = six coins, while 15 + 15 uses two. The habit to build is a quick proof: an exchange argument (swapping any optimal solution's choice for the greedy one never makes it worse) or a "greedy stays ahead" argument. If you cannot find one, consider dynamic programming.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Single pass | O(n) |
| Sort then pass | O(n log n) |
| Greedy with a heap | O(n log n) |
Patterns to recognise
Reachability frontier
Use it for: Jump game I and II, video stitching.
Track the farthest index reachable; count a jump each time you pass the current frontier.
Running balance
Use it for: Gas station, lemonade change.
Track a running surplus; reset the start point when it goes negative.
Sort and match
Use it for: Assign cookies, boats to save people, hand of straights.
Sort both sides and pair smallest-with-smallest (or largest-with-smallest) using pointers.
Code template
def jump(nums):
jumps = 0
current_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end: # must jump to go further
jumps += 1
current_end = farthest
return jumps
int jump(const vector<int>& nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i + 1 < (int)nums.size(); ++i) {
farthest = max(farthest, i + nums[i]);
if (i == currentEnd) { // must jump to go further
++jumps;
currentEnd = farthest;
}
}
return jumps;
}
Common mistakes
- Trusting a greedy idea that only works on the sample — try to break it with a small counter-example first.
- Sorting by the wrong key (start time instead of end time in interval scheduling).
- Ties can matter; decide how equal keys should be ordered.
Quick check
Three questions on Greedy. Get all three right to earn +15 XP.
-
A greedy algorithm makes which kind of choice at each step?
It commits to a locally optimal choice and moves on.
-
Coins are 1, 3 and 4. Greedy "largest coin first" for amount 6 gives 4 + 1 + 1. What does this show?
Greedy needs a proof for each problem. Here dynamic programming is required.
-
Which argument is commonly used to prove a greedy strategy correct?
Show that swapping any optimal solution toward the greedy choice never makes it worse.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Assign CookiesLeetCode Easy +20
- Lemonade ChangeLeetCode Easy +20
- Jump GameLeetCode Medium +40
- Jump Game IILeetCode Medium +40
- Gas StationLeetCode Medium +40
- Partition LabelsLeetCode Medium +40
- Hand of StraightsLeetCode Medium +40
- CandyLeetCode Hard +70
Stuck on Greedy?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor