Greedy & the Exchange Argument

What greedy means

A greedy algorithm makes the best-looking choice at each step and never reconsiders it. No table of subproblems, no backtracking — commit and move on. When it applies, it is the simplest and fastest tool in the box, usually one sort plus one linear scan. The catch: greedy is only correct for problems with a special structure, and interviewers love probing whether you know the difference between "greedy feels right" and "greedy is provably right".

The exchange argument

The standard proof technique is the exchange argument: take any optimal solution, show you can swap one of its choices for the greedy choice without making it worse, and conclude greedy loses to nothing.

Concrete example — activity selection: given meetings, attend as many non-overlapping ones as possible. The greedy rule: sort by end time, then repeatedly take the earliest-ending meeting that does not clash with what you have already taken.

Meetings (start, end): (1,4), (3,5), (0,6), (5,7), (5,9), (8,9). Sorted by end time they are already in this order. Take (1,4). Skip (3,5) and (0,6) — they overlap it. Take (5,7). Skip (5,9). Take (8,9). Three meetings.

Why can this never lose? Suppose some optimal schedule OPT picks a different first meeting, one ending at time e. Greedy's first pick ends at the earliest time of all, so it ends at or before e. Swap it into OPT in place of OPT's first meeting: it finishes no later, so everything after it in OPT still fits. OPT's count is unchanged — we exchanged one meeting for one meeting. Repeat the swap down the line and OPT transforms into the greedy schedule with the same count. Greedy is optimal.

That is the whole pattern: any optimal solution can be massaged, one no-cost swap at a time, into the greedy one. In an interview you rarely write this formally — a two-sentence version ("swapping in the earlier-ending meeting can only leave more room; count unchanged") is exactly the level expected.

The sort key is the proof

Greedy usually starts with a sort, and the key is where correctness lives. Sorting activities by start time fails: (0,10) starts first, greedy grabs it, and blocks (1,2), (3,4), (5,6). Sorting by shortest duration also fails on crafted inputs. Only end time survives the exchange argument. When you propose a greedy, name the sort key and say why that key makes the swap safe.

Kadane's: extend or restart

Maximum Subarray — the largest sum of any contiguous run — is greedy in disguise. Walk left to right keeping cur, the best sum of a subarray ending here:

cur = 0
best = float("-inf")
for x in a:
    cur = max(x, cur + x)   # extend the run, or restart at x
    best = max(best, cur)

The choice at each element: extend the previous run or abandon it and restart. The no-regret reasoning: if the running sum before x is negative, dragging it along can only hurt — any subarray that keeps it would improve by cutting it off. On [-2, 1, -3, 4, -1, 2, 1, -5, 4], cur goes -2, 1, -2, 4, 3, 5, 6, 1, 5 — best is 6, from [4, -1, 2, 1].

Reach problems: Jump Game

Jump Game: nums[i] is your max jump length from index i; can you reach the end? Greedy: sweep once, tracking the furthest reachable index.

reach = 0
for i, n in enumerate(nums):
    if i > reach: return False   # standing beyond anything reachable
    reach = max(reach, i + n)
return True

[2,3,1,1,4] reaches; [3,2,1,0,4] strands you at the 0. Jump Game II (minimum jumps) layers on one idea: treat indices covered by the current jump as a layer, like BFS levels. Track farthest seen and the current layer's boundary end; when i hits end, you must jump — increment the count and set end = farthest. The classic bug is incrementing jumps on every improvement of farthest instead of only when crossing the boundary.

Gas Station: reset plus a global check

Gas Station: circular route, gas[i] fuel at station i, cost[i] to reach the next. Find a valid starting station. Two facts make it greedy:

1. Global feasibility: if total gas ≥ total cost, a valid start exists (and it is unique when totals differ appropriately). If not, no start works.
2. Reset rule: if starting at i you first go negative arriving at station j+1, then no station in i..j can work either — each of them would arrive at j+1 with no more fuel than you had. So restart the candidate at j+1 and never look back.

total = tank = start = 0
for i in range(n):
    diff = gas[i] - cost[i]
    total += diff
    tank += diff
    if tank < 0:
        start = i + 1   # everything before j+1 is disqualified
        tank = 0
return start if total >= 0 else -1

One pass, and the failure proof is again an exchange-style "nothing skipped could have been better".

When greedy is wrong: the counter-signals

The canonical failure: coin change with coins [1, 3, 4] and amount 6. Greedy grabs the biggest coin: 4 + 1 + 1 = three coins. Optimal is 3 + 3 = two. The greedy choice (take a 4) interacts with future choices (it ruins the ability to use two 3s), and no exchange argument can rescue it — this needs DP.

Reach for DP instead of greedy when you see:

The interview script

When you propose a greedy: (1) state the rule in one sentence, including any sort key; (2) give the two-sentence no-regret argument; (3) name the failure mode you checked — "this is not a counting question, and choices do not interact". A greedy without a stated argument is a guess; the argument, even informally, is what earns the pattern.