4.26.0 — Greedy: The Pattern

Recognition cue. The problem asks for a best or a fewest, and there is an obvious locally-best move at each step.

The move. Take that move, never reconsider it, and finish in one pass.

The catch, and it is the whole chapter: greedy is only correct when you can prove the local move is part of some optimal answer. An unproved greedy is a guess, and a guess that passes the sample tests is worse than a correct O(n^2).

The two-step test

Step 1 — hunt for a counterexample, for thirty seconds. Take your greedy rule and try to break it. Coin Change with coins [1,3,4] and target 6 breaks "take the biggest coin". If you find a counterexample, it is DP (4.22).

Step 2 — if you cannot break it, prove it. There are only two proof shapes, and both are short.

The exchange argument. Take any optimal solution. Show that swapping its first choice for the greedy choice leaves it no worse. Repeat, and greedy becomes optimal.

Maximum Subarray: if the running sum is negative, any subarray spanning it is improved by dropping the negative part. So restarting is safe.

The domination argument. Show that after k steps, greedy's position is at least as good as any other strategy's after k steps.

Jump Game II: greedy's reach after k jumps is at least any strategy's reach after k jumps, so it never needs more jumps.

The easiest greedy of all: no choice

Some problems have a forced move — there is only one legal option, so there is nothing to prove beyond that.

• Hand of Straights — the smallest remaining card must start a group; nothing smaller can precede it.
• Partition Labels — a part must reach the last occurrence of every letter in it.
• Merge Triplets — a triplet with an over-large component can never be used, so discard it.

Recognising a forced greedy is worth saying out loud, because it is a much stronger claim than "this seems to work".

The three shapes

# 1. RUNNING BEST — carry one number, reset when it stops helping
best_here = best_overall = a[0]
for x in a[1:]:
    best_here = max(x, best_here + x)          # extend or restart
    best_overall = max(best_overall, best_here)

# 2. FURTHEST REACH — extend the boundary, act when you hit it
end = furthest = 0
for i in range(len(a)):
    furthest = max(furthest, i + a[i])
    if i == end:
        act(); end = furthest

# 3. SORT, THEN SWEEP — the order makes the choice obvious
for x in sorted(items, key=...):
    if compatible(x): take(x)

Shape 2 covers Jump Game II, Partition Labels, Video Stitching and Minimum Taps — four problems with almost identical code and completely different stories.

The eight problems

#	Problem	Why greedy is safe
4.26.1	Maximum Subarray ★	A negative prefix can be dropped without loss
4.26.2	Jump Game ★	Reachability is downward closed, so one number describes it
4.26.3	Jump Game II	Greedy's reach dominates after every jump
4.26.4	Gas Station	A failure rules out every start in the stretch
4.26.5	Hand of Straights	Forced — the smallest card must start a group
4.26.6	Merge Triplets	Monotonic operation: overshoot is permanent
4.26.7	Partition Labels	The boundary is forced by last occurrences
4.26.8	Valid Parenthesis String	The set of possible counts is a contiguous range

★ marks the Blind 75 subset.

Where greedy quietly fails

Worth memorising, because these are the traps:

• Coin Change with arbitrary denominations — [1,3,4], target 6.
• 0/1 knapsack — best value-to-weight ratio first is wrong when items cannot be split. It is right for the fractional version, which is the classic contrast.
• Longest path — greedy and DP both fail; it is NP-hard.
• Anything where a choice now removes an option later — House Robber, Word Break. That dependency is the structural tell for DP.

What the interviewer will push on

"Prove your greedy is correct." Exchange or domination. Have one ready before you write code.

"Can you break it?" Try, out loud. Failing to find a counterexample after honestly trying is itself evidence, and showing the attempt is worth marks.

"Why not DP?" Greedy is O(n) or O(n \log n) against DP's O(n^2) — but only when the proof holds.

"What if the input changed slightly?" Jump Game with backwards jumps stops being greedy and becomes a graph search. Knowing which assumption you relied on is the real test.

One thing to volunteer: state the proof before the code. A greedy solution with no justification reads as a lucky guess, and an interviewer cannot tell the difference between that and understanding.

Recall

• Greedy = take the locally best move and never reconsider. Only correct with a proof.
• Test it by hunting a counterexample for thirty seconds. Found one → DP. Otherwise prove it.
• Two proof shapes: exchange (swapping in the greedy choice leaves an optimal solution no worse) and domination (greedy's state after k steps beats any alternative's).
• The easiest case is a forced greedy — only one legal move, so there is nothing to weigh.
• Three shapes: running best (reset when it stops helping) · furthest reach (extend, act at the boundary) · sort then sweep.
• Greedy fails when a choice now removes an option later — that is the DP tell.
• Fractional knapsack is greedy; 0/1 knapsack is not. The contrast is the classic exam question.

Next: 4.26.1 Maximum Subarray — Kadane's algorithm, and the cleanest exchange argument in the chapter.