1Understand
The idea
Make the choice that looks best right now and never revisit it. That is only correct when you can argue that swapping the greedy choice into any optimal solution keeps it optimal (an exchange argument). The work is usually in finding what to sort by, such as the earliest end, the largest gain or the tightest deadline.
Intuition
Make the choice that looks best right now and never revisit it. That is only correct when you can argue an exchange argument: swapping the greedy choice into any optimal solution keeps it optimal (or improves it).
The work is usually finding what to sort by, earliest end time, largest gain, tightest deadline. If you cannot sketch why a local choice is safe, fall back to DP.
Greedy solutions are often short once the ordering is right; wrong ordering is the usual bug.
What you will be able to do
- Justify the greedy choice
- Spot when greedy fails and DP is needed
When to use it
- Jump game / gas station style reachability
- Minimum number of X to cover Y
- Choosing the earliest-ending option first
2See it
Walkthrough
Jump game reach
a = [2, 3, 1, 1, 4], track farthest reachable index.
1 / 6
reach = 0. Start at i=0 (always reachable).
Live template
Line 4 active
Complexity: time O(n) or O(n log n), space O(1)
Usually O(n log n) with a sort, or O(n) when a linear scan suffices. DP alternatives are often O(n²). Prefer greedy when the exchange argument is clear; otherwise DP is safer.
Read the walkthrough as text
Jump game II (min jumps). nums = [2,3,1,1,4].
- Greedy BFS layers on the array: within the current jump reach, track the farthest you can get.
- When the scan index hits the end of the current layer, bump jumps and set the new layer end to that farthest.
- From index 0, layer end 0, farthest becomes 2; jump → layer end 2.
- Inside 1..2, farthest becomes 4; next jump reaches the end → answer
2.
Choosing the earliest end for interval scheduling is the same "safe local choice" spirit.
3Recognise it
Kinds of problems (11)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Reachability (jump game)
Example. Can you reach the last index from jumps[i]?
How. Track farthest index reachable; fail if i > farthest.
Gas station
Example. Complete a circuit with gas and cost arrays.
How. If total gas ≥ total cost, start from index where tank never goes negative when cycled.
Assign cookies / matching
Example. Maximize children satisfied with smallest cookies.
How. Sort both; two pointers match smallest cookie that fits each child.
Partition labels
Example. Partition string so each letter appears in one part.
How. Record last index of each letter; extend current part to max last seen.
Minimum arrows / platforms
Example. Minimum arrows to burst all balloons (intervals).
How. Sort by end; shoot at end; skip overlapping intervals covered.
Grouping with counts (hand of straights)
Example. Split into groups of k consecutive numbers.
How. Count frequencies; greedily start groups from smallest available keys.
Sort by a derived key (two-city scheduling, deadlines)
Example. Schedule jobs by profit/time or fly to cheaper city first.
How. Sort by deadline or delta; prove greedy choice safe for that key.
Two passes, left and right (candy)
Example. Minimum candies with neighbour rating rules.
How. Left pass increase if rating rises; right pass enforce from the right.
Track a range of possibilities (valid parenthesis string)
Example. Remove min parentheses to make string valid.
How. Track open count range [lo, hi] allowed after each character.
Local fix-ups while scanning (place flowers, non-decreasing array)
Example. Place flowers with gap rule in one pass.
How. Greedy plant when previous two slots empty; or raise arr[i] to arr[i-1] while scanning.
Turn-by-turn simulation with queues
Example. Rotating queue simulation (e.g. queue of tasks).
How. Simulate rounds with deque or counters; greedy pick local optimum each turn.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Unsafe greedy
Why it happens. First local rule that seems optimal often passes small tests.
How it fails. Coin change by largest coin fails [1,3,4] amount 6, greedy is not optimal.
Fix. Prove exchange argument or use DP when counterexample exists.
Wrong sort key
Why it happens. Sorting by start is natural for intervals.
How it fails. Minimum arrows sorted by start, miss overlap chain that sorting by end covers.
Fix. Non-overlap minimisation sorts by end; merge often by start, read variant.
Local check only
Why it happens. Each step feasible so the whole plan feels feasible.
How it fails. Jump game checks jump[i]>0 only, misses that earlier index cannot be reached.
Fix. Carry global invariant (farthest reach, running sum) not just local rule.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.