Greedy Algorithms

What makes an algorithm "greedy"

A greedy algorithm builds a solution one step at a time, and at each step makes the choice that looks best right now — then never revisits that choice. No backtracking, no "let me also keep the second-best option around in case it pays off later." Contrast this with Dynamic Programming: DP also builds a solution incrementally, but it explores (or implicitly remembers, via a table) multiple candidate choices at each state and lets the recurrence pick the winner after the fact. Greedy commits early; DP defers the decision until it has enough information to prove which option is actually best.

This is why greedy solutions are almost always shorter and faster than the DP solution to the same-shaped problem when they apply — usually O(n log n) instead of O(n²) or worse — and also why they're dangerous: a greedy algorithm that hasn't been proven correct is just a guess that happens to pass the examples in front of you.

The core interview skill: proving greedy is safe, not guessing

Anyone can propose "sort it and take things in order" for a new problem. The skill that separates a Senior candidate is being able to say why that greedy choice can't lose — out loud, before writing code. You don't need a formal proof at the whiteboard, but you do need one of these two informal arguments in your back pocket:

• Exchange argument. Assume some optimal solution O differs from your greedy solution G at the first point where they disagree. Show that you can swap O's choice for G's choice at that point without making O worse (and without breaking feasibility). Since the swap doesn't hurt, you can repeat it until O becomes G — meaning G was optimal all along. This is the classic proof for interval scheduling: swap the optimum's first-chosen activity for the one with the earliest finish time; the swap only frees up more room for everything after it, so it can't make things worse.
• Greedy stays ahead. Define a measure of progress (e.g., "farthest index reachable so far," "gas remaining in the tank"), and show that at every prefix of the input, greedy's value for that measure is at least as good as any other valid strategy's. If greedy never falls behind at any point, it can't lose at the end either. This is the natural argument for Jump Game–style reachability problems and Gas Station, where there's a running state rather than a sorted list to pick from.

You don't need to write these as formal induction proofs in an interview — stating the shape of the argument in one or two sentences ("I'll sort by end time and use an exchange argument: swapping in the earliest-finishing option never costs us room for later choices") is exactly the signal that separates "I found the pattern that matches this problem" from "I actually understand why this works."

Building block 1: sort by the right key

The overwhelming majority of greedy problems begin with a sort, and the entire difficulty is figuring out what key to sort by. Common keys:

• Earliest finish/end time — interval scheduling, meeting rooms, activity selection.
• Ratio of two quantities — value-to-weight (fractional knapsack), profit-to-effort.
• A single dominant attribute after a symmetry-breaking tie-break — e.g., sort by start time, and when starts tie, sort by end time.

Once you've picked the key, the rest of the algorithm is usually a single linear scan making an obviously-local decision (take it / skip it / merge it) — which is exactly why interviewers love this topic: the hard part is invisible (choosing and justifying the key), and the easy part (the scan) is what ends up in your code.

Building block 2: interval scheduling — greedy's flagship pattern

The generic skeleton below is worth memorizing as a shape, not a specific solution — it's the pattern behind activity selection, and it's the same instinct you'll reuse constantly in the upcoming Intervals topic:

The insight generalizes: whenever a problem is "pick the maximum number (or set) of compatible items under a start/end constraint," sorting by end time and greedily taking anything compatible with your last pick is provably optimal (exchange argument). Sorting by start time or by duration instead are the two most common wrong-but-plausible-looking variants — they fail on small counterexamples, which is exactly why you should test your key choice before committing to it (see below).

Building block 3: two-pass for two-sided adjacent constraints

When each index must satisfy both left and right neighbors (Candy is the flagship), don't solve both directions at once:

1. Init everyone to the minimum legal value.
2. Left→right: enforce only the left-neighbor rule.
3. Right→left: enforce the right-neighbor rule with max(...) so you don't break pass 1.
4. Strict > usually means equals are a free edge — no increase required.

Generalizes to: Candy, trapping-rain-water-style L/R bounds, bitonic / mountain "best from each side" merges. Prefer this over "find valleys and expand" — same idea, much easier to prove in a loop.

Sanity-checking a greedy idea before you write code

Before you type anything, spend 60–90 seconds trying to break your own idea with 3–4 small, handcrafted inputs — specifically inputs designed to create conflicts (ties, one huge item, one item that "looks" good locally but blocks something better). If you can't construct a counterexample after genuinely trying, that's meaningful evidence — not proof — that the greedy choice is safe, and it's a much cheaper check than discovering the bug from a failed test case after you've written and debugged 20 lines of code. This is a concrete, practical habit — do it every time you reach for greedy, and narrate that you're doing it. It signals rigor even when your first instinct turns out to be correct.

When greedy fails and you need DP instead

The canonical cautionary tale is knapsack. Fractional knapsack (you may take any fraction of an item) is solved optimally by a pure greedy: sort items by value-to-weight ratio, descending, and fill the knapsack greedily, taking a fraction of the last item if it doesn't fit whole. This works because you can always slice the lower-ratio item you'd otherwise be forced to include, so there's never a reason to prefer a worse ratio.

0/1 knapsack (each item is all-or-nothing) breaks that argument completely — you cannot take 60% of an item, so the greedy choice can lock you into a suboptimal combination with no way to correct it later. Concretely: capacity 10, item A = (weight 6, value 12, ratio 2.0), item B = (weight 5, value 9, ratio 1.8), item C = (weight 5, value 9, ratio 1.8). Greedy takes A first (best ratio), leaving capacity 4 — nothing else fits, total value 12. But B + C together weigh 10 and are worth 18. Once you've committed to A, there's no exchange that fixes it — you'd have to un-take it, which greedy structurally cannot do. This is precisely the shape of problem Dynamic Programming exists for: it keeps every "what if we didn't take this item" branch alive in the DP table instead of discarding it, and picks the winner only once all options have been considered. The same story repeats with coin change (greedy by largest denomination fails for non-canonical coin systems like {1, 3, 4} making 6) and job scheduling with deadlines and non-unit durations.

Complexity analysis

Phase	Typical cost	Notes
Sort by chosen key	O(n log n)	Dominates the overall runtime in almost every greedy problem
Linear scan / greedy decision	O(n) or O(n log n)	O(n log n) if the scan itself needs a heap (e.g., always-take-the-best-remaining-option patterns)
Space	O(1) to O(n)	O(1) if you scan in place after sorting; O(n) if you need auxiliary tracking (last-seen index, running counts)

The headline number to say out loud is O(n log n) time, dominated by the sort — and if an interviewer asks "can we do better than O(n log n)?", the honest answer is usually no, once your algorithm depends on processing items in sorted order (comparison-based sorting is a lower bound unless the key has special structure, e.g. bounded integers enabling counting sort).

Greedy vs. Dynamic Programming: when each applies

Problem shape	Greedy works?	Why
Interval scheduling (max compatible intervals)	Yes	Exchange argument on earliest-finish time; no benefit to ever holding onto a later-finishing choice
Fractional knapsack	Yes	Items are divisible — you can always swap partial low-ratio weight for high-ratio weight
0/1 knapsack	No — needs DP	All-or-nothing items mean an early greedy pick can strand capacity with no way to undo it
Coin change, arbitrary denominations	No — needs DP	Greedy-by-largest-coin fails for non-canonical coin systems (e.g. {1, 3, 4}, target 6)
Job sequencing, unit-time jobs with deadlines/profits	Yes	Sort by profit descending, greedily place each job in its latest available slot before its deadline
Longest increasing subsequence / general subsequence optimization	No — needs DP	The best choice at position i depends on which earlier elements you kept, which greedy can't reconsider

If you can't articulate why a problem is on the left side of this table rather than the right, that's the signal to fall back to Dynamic Programming rather than ship an unproven greedy guess.

Pitfalls and interview gotchas

• Silent tie-breaking bugs. When your sort key has ties (two intervals with the same end time, two items with the same ratio), the "obviously correct" tie-break isn't always obvious — work out on paper whether ties matter for correctness, and if they do, add a secondary sort key explicitly rather than relying on a stable-sort accident.
• Presenting greedy without justifying it. Saying "I'll just sort and take greedily" with no reasoning is a communication red flag at the Senior level, even when the code happens to be correct — interviewers are evaluating whether you can tell correct greedy from lucky greedy, not just whether you can pattern-match.
• Greedy that's locally provable but globally wrong because of a missed constraint. E.g., forgetting that choices must remain feasible (a capacity, a cooldown, a resource limit) in addition to being locally optimal — check both every time.
• Reaching for greedy on optimization problems with overlapping/dependent subproblems. If the best choice at step i depends on which earlier choices you made (not just how many), that's usually a DP smell, not a greedy one.

How to justify greedy out loud

"I'll sort by end time and greedily take the next compatible interval. I can justify this with an exchange argument: if an optimal solution's first pick finishes later than mine, swapping in my earlier-finishing pick can only free up more room for the rest of the schedule, never less — so the swap never hurts, and by induction my greedy choice is safe at every step."

Naming the specific argument (exchange, or greedy-stays-ahead) and tying it to the specific quantity you're optimizing is what turns "I think this works" into "I know this works" — exactly the bar a FAANG Senior loop is checking for.