Greedy Algorithms: When the Obvious Choice Is Right

Make change for 6 cents with coins worth 1, 3, and 4. The greedy move — grab the biggest coin that fits — takes a 4, then a 1, then a 1: three coins. The best answer is two 3s. Greedy just lost, confidently, on a problem a child could eyeball.

That’s the whole tension with greedy algorithms. Finding a greedy choice is never the hard part — “take the biggest coin,” “grab the earliest deadline” — the choices are usually obvious. The hard part, the part the coins just exposed, is that every greedy choice comes with a debt: you owe a reason it won’t strand you later. This hub is about that debt — when you can pay it, and how.

The choice is free. The proof is the work.

A greedy algorithm makes an irreversible local decision at each step and never looks back. When that works it’s wonderful — one pass, no table, no recursion. But unlike a dynamic programming solution, which keeps enough alternative states around to weigh the options, greedy commits and moves on. So the burden it puts on you is a proof: this local choice never paints me into a corner the global optimum could have avoided.

If you can’t make that argument, you don’t have a greedy solution — you have a guess that happens to pass the sample cases. The coin example is exactly that: “take the biggest coin” feels safe until the denominations aren’t nice, and nobody proved it was safe.

The exchange argument

There’s one tool that proves most greedy algorithms, and it’s worth having by name: the exchange argument. The shape is always the same. Assume some optimal solution disagrees with greedy’s first choice. Show you can swap greedy’s choice into that optimal solution without making it any worse. If the swap always works, greedy’s choice was as good as optimal’s — so greedy stays optimal by induction, one decision at a time.

Interval scheduling is the cleanest example. To fit the most non-overlapping meetings in a room, greedily pick the one that ends earliest. Why is that safe? Take any optimal schedule; its first meeting ends no earlier than the earliest-ending one, so swap ours in — it frees up at least as much room, and the rest of the optimal schedule still fits. Nothing got worse, so greedy matches optimal. That’s the argument you’re implicitly making every time greedy is correct; the good habit is saying it out loud.

Reading the NeetCode greedy problems as arguments

What makes these problems “greedy” isn’t the choice — it’s that the choice comes with a one-line reason it can’t backfire. That reason is the part worth rehearsing:

• Jump Game. Sweep left to right tracking the farthest index you can reach; if the loop ever passes that frontier, you’re stuck. Safe because reachability only grows — once a cell is reachable, a better jump seen later can’t un-reach it.
• Jump Game II. Same sweep, but count a jump each time you exhaust the current jump’s range and extend to the farthest you’d seen. It’s really a breadth-first expansion in disguise, which is why it gives the fewest jumps.
• Gas Station. If total gas is at least total cost, a start exists — and it’s the station right after the point where your running tank hit its lowest. Everything before that point drained you; nothing after it can, or the minimum would’ve been later.
• Partition Labels. Extend the current partition to the last occurrence of every character you’ve seen; cut when the loop index reaches that end. Safe because a letter can’t straddle a boundary — if it appears again later, the boundary has to move past it.
• Maximum Subarray. Kadane’s is greedy at heart — though it’s just as often taught as the cleanest 1D DP recurrence — drop the running sum the instant it goes negative, because a negative prefix can only hurt whatever comes next. I trace the full “extend or restart” decision in Maximum Subarray.

Notice none of those reasons is “it worked on the examples.” Each is a sentence about why the discarded options were provably safe to discard. And the payoff for having the sentence is how little code you write — the whole of Jump Game is the argument, typed out:

int farthest = 0;
for (int i = 0; i < nums.length; i++) {
    if (i > farthest) return false;         // the frontier passed us — stuck
    farthest = Math.max(farthest, i + nums[i]);
}
return true;                                // never fell behind the reachable frontier

The other three on NeetCode’s Greedy list — Hand of Straights, Merge Triplets to Form Target Triplet, and Valid Parenthesis String — are the same move in less obvious clothing: each turns on one local decision you can defend in a sentence. I’ll add their arguments as I write them up.

When I let myself trust it

Two signals make me reach for greedy without much anxiety: when sorting first turns the right choice into “just take the front” (earliest deadline, smallest weight), and when I can actually say the exchange sentence. If neither holds — if the local choice might strand me — I stop and reach for DP, which pays more to consider the branches greedy throws away. When it applies, greedy is usually the cheaper reward for that proof — often a single $O(n)$ pass, or $O(n \log n)$ when a sort sets it up, where DP would fill a table.

This is also why real systems lean on greedy even where nobody can prove it optimal. Some caches evict the least-recently-used line; some load balancers hand each request to the least-loaded backend they can see right now. The true optimum would need to see the future — Bélády’s cache needs the next access, the balancer the next arrivals — so they take the defensible local choice and accept a heuristic that’s good enough in practice instead of an unaffordable perfect one. Greedy as an honest engineering compromise rather than a proof.

Greedy is a claim, not a plan

So the discipline is a single sentence longer than the code: when you propose a greedy solution, say the choice and the reason it can’t backfire in the same breath. “Take the earliest-ending interval, because swapping it into any optimal schedule never costs us room.” If that sentence won’t come, treat it as a warning to reconsider — maybe a different proof works, but often the problem really wants DP (or a search) instead, and the coins that add up to 6 are waiting to embarrass a greedy guess.

References

• NeetCode 150 — Greedy — the problems this hub works through.
• One-Pass Algorithms and Greedy Strategies — the single-scan/streaming side of greedy, with a full Kadane trace.