DSA & Algorithms
Part 4 of 16 · DSA Advanced & Company FavoritesGreedy Algorithms - Proof Sketches & Exchange Arguments
When greedy works: exchange arguments, stay-ahead proofs, and classic interview greeds.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
A local choice can be proved safe
Prefer
Sort and take the feasible best
The proof is an exchange or a stay-ahead argument.
- Jump game extends the farthest reach.
- Interval erase keeps the earliest end.
- If the proof fails, stop and use DP.
Alternative
Search every combination
Correct, and slower than the sort-and-scan the interviewer expects.
- You never name why the choice is safe.
- You sort by the wrong key.
- You call it greedy with no invariant.
Choose, then justify
No proof means it is not the answer yet.
- 1
Sort by the decision key
End time, reach, or ratio. Say which. - 2
Take the feasible best
Skip choices that break the invariant. - 3
Prove or switch
Exchange argument, or move to DP.
Overview
When greedy works: exchange arguments, stay-ahead proofs, and classic interview greeds.
When companies ask this
Recognition cues: min/max after sorting; jump game; gas station; activity selection; assign cookies; partition labels.
Company asks: Meta Jump Game; Amazon gas/intervals; Google expects a proof sketch.
Mental model
Decisions
- 1
Step 1 Define the local choice
- nextStep 2 Does the choice need an order?
- ?
Step 2 Does the choice need an order?
- yesStep 3a Sort by the key the proof uses - end time, ratio
- noStep 3b Single pass with running state
- 3
Step 3a Sort by the key the proof uses - end time, ratio
- nextStep 4 Take the best feasible item, never undo
- 4
Step 3b Single pass with running state
- nextStep 4 Take the best feasible item, never undo
- 5
Step 4 Take the best feasible item, never undo
- nextStep 5 Exchange or stays-ahead proof holds?
- ?
Step 5 Exchange or stays-ahead proof holds?
- yesStep 6 Greedy is optimal
- noFailure path - find a counterexample, then try DP or search
- 7
Step 6 Greedy is optimal
- 8
Failure path - find a counterexample, then try DP or search
Lesson map
Greedy Algorithms - Proof Sketches & Exchange Arguments
When greedy works: exchange arguments, stay-ahead proofs, and classic interview greeds.
Architecture. Step 1 Define the local choice Ready. Step 2 Does the choice need an order? Ready. Step 3a Sort by the key the proof uses - end time, ratio Ready. Step 3b Single pass with running state Ready. Step 4 Take the best feasible item, never undo Ready. Step 5 Exchange or stays-ahead proof holds? Ready. Step 6 Greedy is optimal Ready. Failure path - find a counterexample, then try DP or search Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB S["Step 1 Define the local choice Ready"] O["Step 2 Does the choice need an order? Ready"] R["Step 3a Sort by the key the proof uses - end time, ratio Ready"] T["Step 3b Single pass with running state Ready"] P["Step 4 Take the best feasible item, never undo Ready"] V["Step 5 Exchange or stays-ahead proof holds? Ready"] OK["Step 6 Greedy is optimal Ready"] X["Failure path - find a counterexample, then try DP or search Ready"] S -->|continues| O O -->|yes| R O -->|no| T R -->|continues| P T -->|continues| P P -->|continues| V V -->|yes| OK V -->|no| X
Exchange argument: Transform any OPT into greedy G by swapping first differing choice without worsening cost.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Usually O(n log n) + O(n). Jump Game O(n).
- Wrong sort key; no total-gas check; greedy without proof.
Interviewer traps
LeetCode drill (real problems)
- Jump Game
- Jump Game II
- Gas Station
- Non-overlapping Intervals
- Assign Cookies
- Candy
- Queue Reconstruction by Height
- Minimum Number of Arrows to Burst Balloons
- Partition Labels
YouTube
Interview Q&A
When greedy safe?
Answer
Greedy choice property + optimal substructure (prove).
Jump invariant?
Answer
reach farthest; fail if i>reach.
Why sort by end?
Answer
Free timeline earliest; exchange argument.
Gas station?
Answer
If total>=0 a valid start exists (LeetCode guarantees it is unique); reset start and tank when the tank goes negative.
Greedy vs DP?
Answer
If a counterexample beats the greedy pick, try DP or search, whichever fits the state.
Candy?
Answer
Two passes L->R and R->L.
Huffman?
Answer
Merge two smallest via heap.
Related wave-1?
Answer
sorting-intervals, heaps, dp-1d.