L49 · Greedy — And Proving It Works

Series: LeetCode — From Basics to Interview-Ready · Session 49 / 65 · Phase 3 · Advanced & specialised

Watch first

These are pre-reads, not substitutes for the solve. Watch them before you open the editor, at 1.5x, and stop each one the moment the rule is stated — the derivation is your job, not the video's.

Why this session exists

Greedy is dangerous precisely because it feels right. Every other pattern in this series announces itself — you either see the sliding window or you do not. Greedy is different: your brain produces a plausible rule instantly, the rule works on the sample input, and you have no signal that anything is wrong until the submission fails on test 47.

So this session inverts the usual order. Instead of learning to recognise greedy problems, you learn to attack your own greedy rule before writing a line of code. The discipline is: state the rule in one sentence, then spend two minutes actively trying to break it with a three or four element input. If you cannot break it in two minutes, either prove it with an exchange argument or accept the risk knowingly. If you can break it, you have saved yourself twenty minutes and learned that the problem is DP.

That two-minute counter-example hunt is the single most valuable habit in this session, and it is cheap. Small inputs are where greedy fails, because that is where a locally attractive choice can consume a resource that a globally better solution needed.

The proof technique worth knowing is the exchange argument. Take any optimal solution, show you can swap its first decision for the greedy's first decision without making it worse, and repeat. If every swap is safe, the greedy solution is as good as the optimum. It is a short argument, it applies to most greedies that are actually correct, and being able to say it aloud is a real differentiator in an interview — most candidates assert their greedy works and cannot say why.

Blank-file warm-up

Five minutes, empty file, no notes. This one is not code. Write, in words:

1. The exchange argument, in three sentences.
2. A greedy rule you have seen fail, and the input that broke it.
3. The two questions you ask of any greedy rule before coding it.

For point 3, mine are: does taking the locally best option ever consume a resource a better solution needed, and is there a case where a worse-looking immediate choice unlocks a much better later one. Both are questions about whether choices interact.

Pattern anatomy

There is no template. That is the honest answer and pretending otherwise would be useless. What there is instead is a procedure, and it is worth following literally:

1. State the rule in one sentence. "At each step, take the interval that ends earliest." If you cannot compress it to a sentence, you do not have a greedy, you have a heuristic.
2. Hunt for a counter-example for two minutes. Three or four elements. Deliberately construct a case where the greedy choice blocks something better.
3. If you cannot break it, attempt the exchange argument. Given an optimal solution that differs from the greedy at the first decision, can you modify it to match the greedy without loss?
4. If the exchange works, code it. If it visibly fails, the problem is DP or search.

The structural condition that makes greedy valid is the greedy choice property: there exists an optimal solution containing the greedy's first choice. Combined with optimal substructure — the remaining problem after that choice is the same kind of problem — you get correctness by induction.

Here are the four canonical greedies from today's problem set, each with its rule stated explicitly:

def jump_game_ii(nums):
    """Rule: within the current reach, extend to whatever reaches furthest."""
    jumps = 0
    current_end = 0      # boundary of the current jump's reach
    farthest = 0         # furthest index reachable with one more jump
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:          # must jump now
            jumps += 1
            current_end = farthest
    return jumps
 
def can_complete_circuit(gas, cost):
    """Rule: if you run dry at station i, no start between the old start and i works."""
    if sum(gas) < sum(cost):
        return -1
    start, tank = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start
 
def partition_labels(s):
    """Rule: a partition can close only at the last occurrence of every letter inside it."""
    last = {c: i for i, c in enumerate(s)}
    out, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            out.append(end - start + 1)
            start = i + 1
    return out

Each of these is under ten lines, and in each case the entire difficulty is convincing yourself the rule is correct. The code is trivial once you believe it.

The cue

You are looking at a greedy problem when the statement contains these tells:

1. "Minimum number of steps / jumps / removals / platforms." A counting objective where each step is a discrete choice. Often greedy, sometimes BFS, occasionally DP.
2. A natural ordering exists — by end time, by deadline, by ratio, by size. If sorting by something obvious makes the problem feel easy, that feeling is either the greedy working or the trap.
3. n is large — 10^5 or more — and the problem looks like DP. DP would be quadratic and too slow, so if a solution exists it is probably linear, and linear usually means greedy or two pointers. The constraint rules out the alternative.
4. "Is it possible to..." rather than "what is the best...". Feasibility questions are often greedy because you only need to exhibit one valid arrangement.
5. A resource that is consumed and cannot be recovered — fuel, time, capacity. Greedy works when each unit consumed is interchangeable.

Tell 3 is the most reliable signal in practice. Large n on a problem with an obvious DP formulation is the setter telling you the DP is not the answer.

Guided solve

Jump Game II — each element is the maximum jump length from that position. Return the minimum jumps to reach the last index. You may assume it is always reachable.

The DP formulation is immediate: dp[i] is the minimum jumps to reach index i, computed by checking every predecessor that can reach i. That is O(n²) and correct. State it, then look at the constraints: n up to 10^4 makes it borderline, and any larger and it is out. So there should be a linear solution.

Now the greedy. The naive greedy rule is "always jump as far as possible", and this is the moment to run the counter-example hunt rather than start typing.

Try [2, 3, 1, 1, 4]. Jump-furthest from index 0 means jumping 2 steps to index 2, which has value 1, so then index 3, then index 4. Three jumps. But the optimal is index 0 to index 1 to index 4 — two jumps, because index 1 has value 3 and reaches the end directly. The naive greedy is broken, on a five-element input, in under a minute.

That failure is informative rather than fatal. It tells you the wrong quantity is being maximised. You should not maximise distance travelled by this jump; you should maximise the furthest position reachable after this jump. Those are different: landing on index 1 travels less far but opens up more.

The correct rule: think of the array in levels, like BFS. Level 0 is index 0. Level 1 is everything reachable in one jump. Level 2 is everything reachable from any index in level 1. The answer is the level containing the last index — this is literally breadth-first search, and it is the reason the greedy is provably correct.

The implementation collapses the BFS into a single pass with two pointers. current_end is the right boundary of the current level. farthest is the right boundary of the next level, updated as you scan. When i reaches current_end, you have seen every index in the current level, you know exactly how far the next level extends, so you increment the jump count and move the boundary.

Two details:

Loop to n - 1, not n. If i reaches the last index and it happens to equal current_end, you would increment the count for a jump you never needed to take. Excluding the final index avoids the off-by-one cleanly.

No explicit reachability check. The problem guarantees the end is reachable. If it did not — as in Jump Game I — you would need to detect farthest <= i and bail out.

Trace [2, 3, 1, 1, 4]. i=0: farthest = 2; i == current_end = 0 so jumps = 1, current_end = 2. i=1: farthest = max(2, 4) = 4. i=2: farthest stays 4; i == current_end = 2 so jumps = 2, current_end = 4. i=3: loop ends since n-1 = 4. Answer 2. Correct.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Gas Station — before coding, spend two full minutes trying to break the rule "if you run dry at i, restart at i+1". Then either prove it or find the break. The proof is in the callout above; do not read it until your timer fires.
• Task Scheduler — arrange tasks with a cooldown between identical ones. The formula involves only the most frequent task's count and how many tasks tie for that frequency. Derive it by drawing the schedule as a grid of rows.
• Partition Labels — partition a string so each letter appears in at most one part. Precompute last occurrences; the rest follows.

Common failure modes

Trusting the first greedy rule that comes to mind. This is the meta-failure and it causes all the others. Two minutes of counter-example hunting is cheaper than twenty minutes of debugging a wrong approach.

Maximising the wrong quantity. Jump Game II is the perfect example — maximise reach after the jump, not the length of the jump. When your greedy fails, ask what you should have been maximising instead; that question usually produces the fix.

Assuming a local optimum composes. Two greedy steps that are each individually best can jointly be worse than two suboptimal steps. This is exactly what optimal substructure rules out when it holds, and exactly what makes greedy fail when it does not.

Sorting by the wrong key. Covered in L48, and it recurs here. By end for scheduling, by ratio for fractional knapsack, by deadline for job sequencing. The key encodes the exchange argument.

Missing the global feasibility check. In Gas Station, if total gas is less than total cost, no start works at all and the scanning greedy would still return an index. One sum check up front.

Not stating the proof. Even when the code is right, an interviewer asking "why does that work" and receiving "it just does" is a meaningfully worse outcome than the same code with a two-sentence exchange argument.

Complexity

Greedy solutions are typically O(n) or O(n log n) — a single pass, or a sort followed by a single pass. That is the whole appeal, and it is why greedy is the intended answer when constraints rule out quadratic.

Jump Game II: O(n) time, O(1) space. One pass, three integers. The DP alternative is O(n²) time and O(n) space, which is the gap the greedy buys you.

Gas Station: O(n) time, O(1) space. One pass for the feasibility sum, one for the scan — or both in the same pass if you prefer.

Task Scheduler: O(n) time, O(1) space with a fixed 26-letter alphabet. The formula version does no sorting at all; the heap simulation is O(n log 26) which is also effectively linear but with a much larger constant.

Partition Labels: O(n) time, O(1) space — one pass to record last occurrences into a fixed-size map, one pass to partition.

The pattern is consistent: greedy trades proof obligation for an order of magnitude in runtime. When the proof holds, that is an excellent trade.

Timing rubric

This is a 75-minute session. Budget it explicitly, because greedy sessions have a failure mode where you spend an hour reading proofs and write no code.

• 0–5 min · Blank-file warm-up. Three written answers, no code.
• 5–20 min · Jump Game II guided. Counter-example hunt first (2 min, hard stop), then the level/BFS reframe, then code.
• 20–35 min · Gas Station solo, timed. Two minutes of attack on the restart rule. If you have not broken it by 2:00, write the exchange argument in one sentence and code it.
• 35–50 min · Task Scheduler solo, timed. Derive the formula from a grid drawing. If you are still stuck at 12 minutes, switch to the heap simulation — a correct O(n log 26) beats a half-derived formula.
• 50–62 min · Partition Labels solo, timed. This should take under 12 minutes. If it takes longer, the gap is last-occurrence precomputation, not greedy.
• 62–75 min · Proof pass. Go back to each of the four and say the exchange argument out loud. Anything you cannot say aloud gets logged hint regardless of whether the code passed.

The hard rule: no editorial before your per-problem timer fires. Reading the editorial at minute 6 of a 15-minute block teaches you the answer and nothing else.

Self-scoring checklist

Score each problem after you finish it, before you move on. Two points each.

1. Rule stated in one sentence, before coding? (2 = written down; 1 = said in your head; 0 = you started typing.)
2. Counter-example hunt actually run for a full two minutes? (2 = you constructed at least two candidate inputs; 0 = you skipped it.)
3. Exchange argument articulated? (2 = you could say it out loud unaided; 1 = you needed the callout; 0 = "it just works".)
4. Correct on first submission? (2 = clean; 1 = one fix; 0 = more.)
5. Complexity stated unprompted, both time and space? (2 = yes; 0 = no.)

8–10 → log cold, 60-day interval. 5–7 → warm, 21 days. 3–4 → hint, 7 days. 0–2 → failed, 2 days then 7.

The scoring exists because greedy has an unusually wide gap between "passed" and "understood", and only the second one transfers to a problem you have not seen.

Problem set with company attribution

Company tags below come from each problem's own LeetCode company-tag listing — treat them as "has been reported here", not a guarantee of what you will be asked.

• Jump Game II (45) — Medium · tagged Amazon, Google, Microsoft · the reach-vs-length correction.
• Gas Station (134) — Medium · tagged Amazon, Bloomberg, Google · the proof-heavy one.
• Task Scheduler (621) — Medium · tagged Facebook/Meta, Amazon · formula vs. heap simulation.
• Partition Labels (763) — Medium · tagged Amazon, Facebook/Meta · forced-rule greedy.
• Jump Game (55) — Medium · the feasibility sibling; needs the farthest <= i bail-out that LC 45 does not.
• Non-overlapping Intervals (435) — Medium · sort-by-end scheduling, the textbook exchange argument.
• Minimum Number of Arrows to Burst Balloons (452) — Medium · same exchange argument, different framing.
• Candy (135) — Hard · two-pass greedy; the case where one pass is provably insufficient.

Recovery scripts

Blanking mid-interview on a greedy problem has a specific shape: you have a rule, you do not trust it, and you freeze. These are the sentences to say out loud. Saying something structured beats silence, and interviewers score the process.

If you cannot find any rule at all:

"Let me start with the brute force so we have a correct baseline. I'd enumerate every choice sequence — that's exponential, clearly too slow for these constraints, but it gives me something to check a faster idea against. Now let me look at what the constraints are ruling out."

If you have a rule but suspect it is wrong:

"My candidate rule is: at each step, take X. Before I code it, let me spend a minute trying to break it. I'm looking for a small case where taking X consumes something a better solution needed."

This is the single highest-value sentence in the session. It converts "I'm stuck" into visible, structured work, and it is exactly what a senior engineer does.

If you find the counter-example and your idea collapses:

"Good — that breaks it. That tells me choices interact here, which rules out greedy and points at DP. Let me define the state."

A broken greedy is information, and framing it that way is a strength signal, not an admission of failure.

If the interviewer asks "why does that work" and you have no proof:

"I don't have a full proof yet. The intuition is that swapping an optimal solution's first choice for mine shouldn't make it worse, because [reason]. If you'd like, I can verify it against a brute force on all inputs up to length six — that's about ten lines."

Never say "it just works." Naming the exchange argument as the thing you would prove, even without completing it, demonstrates you know what correctness means here.

If you are past the halfway mark with nothing running:

Abandon elegance and ship the DP. A correct O(n²) that you can then discuss optimising is strictly better than an unfinished greedy. Say: "I'll implement the quadratic DP first so we have something correct, then optimise if there's time."

Common failure modes in the room

Distinct from the algorithmic failure modes above — these are the ones that cost points even when your code is right.

Silent counter-example hunting. You do the right thing but do it in your head, so the interviewer sees ninety seconds of staring. Narrate it.

Coding before the rule is stated. You end up debugging a rule you never articulated, which is unfixable, because you cannot tell whether a failing test means a bug or a wrong rule.

Over-proving. Spending eight minutes on a rigorous exchange argument for Partition Labels, where the rule is forced and one sentence suffices. Match proof depth to how surprising the rule is.

Not stating complexity until asked. Say it as you finish. It costs four seconds and it is on the rubric.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

For greedy problems, add one extra criterion: if you produced correct code but could not state why the rule works, log it as hint at best. The proof is the transferable part; the code is not.