The best bite now,
and never look back

A greedy algorithm makes a sequence of choices, and at each choice it picks whatever looks best right now, by some simple local rule: the largest coin, the earliest-ending meeting, the furthest reach. Crucially, it never revisits a choice. No recursion tree, no undo, no table of subproblems. The entire state is usually one or two variables riding along a single scan.

That's why greedy solutions are so short they look like typos. Jump Game II Medium — a problem people reach for BFS or DP on — is a loop, two variables, and a counter. The hard part was never the code; it's the license to write it.

You've already used greedy without the name. Chapter 7's interval merging sorted by start and swept forward, never reconsidering. Chapter 17's Dijkstra expands the cheapest frontier node and settles it, permanently — that's a greedy choice backed by a proof (no negative edges means the cheapest frontier node can't be improved later). Greedy isn't exotic; it's the default shape of "sort, then sweep."

Here's the entire theory of greedy algorithms, in plain words. Suppose some optimal solution exists that disagrees with your greedy choice at some step. If you can show that swapping the optimal solution's choice for your greedy choice never makes it worse, then step by step you can rewrite any optimal solution into the greedy one without losing anything — so the greedy answer is optimal too. That's the exchange argument, and in an interview it's one sentence, not a proof by induction.

Watch it work on interval scheduling — "attend as many non-overlapping meetings as possible." The greedy rule: always take the meeting that ends earliest. The exchange sentence: "If an optimal schedule takes some other first meeting, swapping it for the earliest-ending one frees up at least as much of the future — so the swap can't hurt." Done. That's a real proof, compressed to something you can say out loud while drawing two intervals on the whiteboard.

And watch it fail on coin change with coins {1, 3, 4}: "taking the biggest coin leaves at least as good a remainder" is simply false — taking the 4 from 6 leaves 2 (two more coins), while taking a 3 leaves 3 (one more coin). No exchange sentence exists, because the claim isn't true. When the sentence won't come out of your mouth, that's not a failure of eloquence. It's the problem telling you it belongs to Chapter 20.

Jump Game Medium: each cell holds a maximum jump length; starting at index 0, can you reach the last index? The backtracking instinct says "try every jump from every cell" — exponential. The greedy insight says you don't care which jumps you take, only how far it's possible to get. So keep one variable, reach — the furthest index any visited cell can launch you to — and scan left to right, extending it: reach = max(reach, i + nums[i]).

Two outcomes. If the ribbon of reachable cells ever falls short of your current index — a gap — you're stuck, and no cleverness would have saved you: nothing to the left could reach past the gap either (that's the exchange argument, disguised as geometry). If reach touches the last index, you're done. O(n) — one pass, no backtracking — and O(1) space.

Run the second array and watch the failure mode: [3,2,1,0,4] funnels every path into the zero at index 3, the ribbon stalls at reach 3, and index 4 sits in the gap. The widget isn't simulating jumps — it's running the actual one-pass algorithm, which never chooses a jump at all. That's the signature of reach-style greedy: track the frontier of the possible, not any particular path.

Jump Game II Medium upgrades the question: the end is definitely reachable — now reach it in the minimum number of jumps. "Minimum number of steps" should ring Chapter 15's bell: on an unweighted graph, that's BFS, and BFS counts layers. Here's the beautiful part — on an array, each BFS layer is a contiguous window of indices, so you never need a queue.

Layer 0 is index 0. Layer 1 is everything reachable in one jump: indices 1 through nums[0]. Layer 2 is everything reachable from anywhere in layer 1. So you scan with two variables: window_end, the last index of the current layer, and farthest, the best reach seen from inside it. When your scan index walks off the end of the window, you were forced to spend a jump — jumps += 1, and the next window ends at farthest. The greedy rule "jump to whatever extends reach the most" never blocks a better plan, because a shorter-reaching jump lands in a subset of the same next layer. That's the exchange sentence.

The full code — both the reach scan and the reach window, in Python and Scala — is waiting in section 9. It's shorter than this paragraph.

Gas Station Medium: stations on a circular route; station i gives you gas[i] and driving to the next one costs cost[i]. Find a starting station from which you can complete the full circuit, or report that none exists. Brute force tries all n starts at O(n²). Greedy does it in one linear pass, using two observations that both sound too good to be true:

• The reset insight. Start at s, run the tank, and suppose it first goes negative at station i. Then no start between s and i can work either — any such start reaches i with at most the fuel you had (you arrived at it with a non-negative tank; they arrive with an empty one). So don't retry them: skip the candidate start straight to i + 1.
• The feasibility shortcut. If total gas ≥ total cost, some start completes the circuit — guaranteed. So one running total settles "impossible," and the reset logic settles "where."

Maximum Subarray Medium — find the contiguous subarray with the largest sum — is usually filed under DP, but its famous solution, Kadane's algorithm, is a greedy sentence: a negative running prefix can only hurt whatever comes next, so drop it. Keep best_ending_here; at each element either extend the running sum or restart fresh at this element, whichever is larger, and track the best you've ever seen:

best_ending_here = max(x, best_ending_here + x) — one pass, two variables, O(n). The exchange sentence: any optimal subarray that includes a negative prefix can swap it away and only improve. (Chapter 20 will re-derive this same line as a one-dimensional DP recurrence — same formula, two schools of paperwork.)

Two more classic wins, same spirit of "an obvious local rule survives the swap test":

• Hand of Straights Medium — split cards into groups of k consecutive values. Greedy rule: the smallest remaining card has no choice — it must start a group (nothing smaller exists to precede it). So sort, repeatedly take the minimum, and pull out its run of k consecutive values from a count map (ch. 4's tool, moonlighting). Any failure is a real failure.
• Merge Triplets to Form Target Triplet Medium — you may merge triplets by taking coordinate-wise maxima; can you build the target? Greedy rule: a triplet that overshoots the target in any coordinate is poison forever (maxima never shrink) — discard it. Merge everything that isn't poison and check whether each target coordinate was hit. Taking every safe triplet can't hurt, because max is monotone.

Now the cautionary tale, performed live. Coin change: make amount 6 with coins {1, 3, 4}, using the fewest coins. Every human instinct says "take the biggest coin that fits" — and with US currency that instinct happens to be right, which is exactly why it's dangerous: it trains you on a coin system specifically designed so greedy works. Hand the same instinct {1, 3, 4} and it takes the 4, strands itself with 2, and pays three coins for what two can buy.

The widget below runs both algorithms for real — biggest-coin-first on top, the true optimum (computed by the DP you'll meet in Chapter 20) below. Slide the amount around: greedy tells the truth at 5, 7, 8, 9… and lies at 6 and 10. That's the scariest property a wrong algorithm can have — right often enough to pass your first three test cases.

Here's how this plays out live. You spot a scan-left-to-right feel and say: "I think this is greedy — my rule would be always extend the furthest reach." Then, before writing code, you spend sixty seconds earning it: one exchange sentence out loud, one deliberate counterexample hunt on a tiny input with weird values. If both survive, you write six lines and name the cost. If either fails, you say "so the local choice can block a better combination — this is DP" and pivot to Chapter 20's playbook. Both paths score well; the pivot often scores better, because you demonstrated the judgment the whole chapter is about.

Notice the asymmetry with every other pattern in this book: two pointers or BFS are legal whenever they fit; greedy fits often and is legal sometimes. That's why its skeleton, uniquely, starts with a proof step.

The pattern, as a whiteboard skeleton:

1. 1Name the local rule out loud — "always take the largest / earliest-ending / furthest-reaching X." If you can't name one, it isn't greedy.
2. 2Say the exchange sentence: "swapping any optimal choice for mine can't make things worse, because …" — and actually finish the because.
3. 3Hunt a counterexample for thirty seconds — tiny n, adversarial values (the {1,3,4} move). Found one? Retreat to DP (ch. 20), and say why.
4. 4Choose the scan order — plain index order, or a sort (by end time, by size). The rule usually dictates the sort.
5. 5Declare the tiny state — one or two variables (reach, tank, best). If you need a table, you're writing DP in denial.
6. 6Decide the reset case — what happens when the invariant breaks mid-scan (tank < 0 → skip the start; gap in reach → fail).
7. 7Write the one-pass loop and name the cost — O(n), or O(n log n) if step 4 sorted.
8. 8Test the boundaries — single element, all-negative, zeros in the middle. Greedy bugs live at the edges of the scan.

The flagship: Jump Game Medium and Jump Game II Medium, back to back, because the delta between them is the chapter. The first tracks one frontier variable — can the ribbon cover the array? The second adds a window boundary and a counter — the BFS-layers-without-a-queue trick from section 4. Both are O(n) time, O(1) space, and neither ever picks an actual jump: they track what's possible, and let the proof handle the rest.