Greedy — And Proving It Works

Review boundary and corrected contracts

Greedy needs a proof for the specific objective. Jump Game II assumes a reachable last index; otherwise its counter is not an infeasibility detector. Gas Station requires nonempty equal-length arrays. Partition-label storage is constant only for a fixed alphabet.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Build the habit of attacking your own greedy before trusting it, and learn the exchange argument well enough to state it out loud under a tight review.

Series: LeetCode — From Basics to Production-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.

Optional original pre-reads (links retained; availability and timestamps not rechecked):

• Jump Game II — Greedy (LC 45) — The canonical 'maximise reach, not jump length' correction. Pause at 4:00 and try to break the naive rule yourself before he does it for you.
• Gas Station — Greedy (LC 134) — The subtlest proof obligation in today's set: why every station between the old start and the failure point is dead. Watch for the argument, not the code.
• Partition Labels (LC 763) — Greedy where the rule is forced rather than chosen — a partition literally cannot close before the last occurrence. Good contrast with rules you must prove.

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 rejected that rule, not every greedy algorithm. Jump Game II below demonstrates exactly that distinction.

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 under a tight review — most engineers 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 proof works, code it. A failed exchange attempt may need a different proof, a different greedy rule, DP, or search; it does not classify the whole problem.

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 three canonical greedies; Task Scheduler's fourth solution is derived after the solo prompts:

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

The implementations are short; the important work is proving their contracts and invariants, not meeting a line-count target.

Gas Station deserves its own note because its greedy is subtler than it looks. The claim is: if the running tank goes negative at station i, then no station from the current start through i can be a valid starting point. The reason is that every prefix sum from the current start up to just before i was non-negative, so any later start within that window begins with less accumulated fuel than the current start had at that point — and the current start already failed. That is a genuine proof, and being able to give it is what makes the two-line solution credible rather than lucky.

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 and an obvious DP is quadratic. Check whether that DP is too costly for the stated limits. Alternatives include greedy, optimized DP, sorting and data structures; large input alone proves none of them correct.
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 a complexity prompt, not a greedy detector. Count states and transitions before rejecting DP: some DPs are linear.

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 takes O(n²) time. At n=10^4 it considers about fifty million predecessor pairs; whether that fits depends on the environment. Seek a better bound without assuming that constraints alone prove a linear solution exists.

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. This code assumes a nonempty array of nonnegative jump lengths with a reachable last index. For feasibility instead, reject an index when i > farthest before using its jump, and succeed when the reachable frontier covers the last index. Being stuck at the last index is not failure: [0] is already reachable.

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: the last loop iteration updates farthest to 4 without incrementing jumps; then range(4) ends. 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.

Solo answers: cooldowns and forced cuts

For Task Scheduler, tasks have unit duration, one processor is available, every task must execute, and an integer cooldown >= 0 requires that many intervening slots between equal labels. Let N be the task count, F the largest frequency and C the number of labels with frequency F. N slots are necessary for the work; the F occurrences of a most-frequent label need F−1 separated frames of width cooldown+1, followed by a final group of C tied labels. This gives the lower bound (F-1)*(cooldown+1)+C. Fill the frames with other labels, using idle slots only where needed; if there are enough other tasks, they expand the frames instead. Thus the achievable minimum is the maximum of these two bounds. The formula returns a length, not a constructed schedule.

from collections import Counter
 
def least_interval(tasks, cooldown):
    if cooldown < 0:
        raise ValueError("negative cooldown")
    if not tasks:
        return 0
    counts = Counter(tasks)
    most = max(counts.values())
    tied = sum(count == most for count in counts.values())
    return max(len(tasks), (most - 1) * (cooldown + 1) + tied)

AAABBB with cooldown 2 needs 8 slots: A B idle A B idle A B. With cooldown 0 the answer is 6; with distinct tasks the work bound dominates. A tick-by-tick simulation of two A tasks and a huge cooldown is slow because it visits every idle slot; the formula does not.

For Partition Labels, the last-occurrence map forces the earliest valid cut: every character seen in a part must finish by the current right boundary. If the scan has not reached that boundary, cutting would split a character; when it does, closing immediately cannot constrain later parts. Inductively this maximizes the number of parts. For abac, the lengths are [3,1]; all-distinct input yields ones, and empty input yields [].

For Gas Station, write d[i] = gas[i]-cost[i]. Failure from candidate s at i means the sum over s..i is negative, while every earlier prefix from s is nonnegative. Removing such a prefix cannot turn that failed suffix nonnegative, so every start s..i is eliminated. After the global nonnegative-total check, the last candidate lies immediately after a minimum prefix sum; the remaining suffix and the wraparound prefix are both feasible. For gas=[1,2,3,4,5], cost=[3,4,5,1,2], it returns 3. Multiple valid starts are allowed by the implementation; it returns one, not a claim of uniqueness.

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. Optimal substructure says an optimal solution uses optimal subsolutions after a decision; it does not say a locally attractive decision is safe. Greedy additionally needs a proof that its chosen decision can belong to an optimum.

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, a reviewer 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.

Myth: If a greedy algorithm produces the correct answer on every test case you can think of, it is correct.

Why: Hand-picked successes do not prove a rule. On [2,3,1,1,4], jumping the greatest immediate distance needs three jumps while the optimum needs two. Exhaustive comparison against an independent oracle on a bounded domain can refute a rule or establish correctness on that domain only. It cannot prove correctness for longer arrays or larger values; the BFS-layer argument establishes the general result here.

Steps 1: Because a greedy algorithm commits to a choice without examining the consequences, its correctness depends entirely on that choice never foreclosing a better outcome.

Steps 2: Because 'never forecloses' means some optimal solution agrees with the greedy on that first choice, this is exactly the greedy choice property.

Steps 3: Because you can demonstrate that property by taking any optimal solution and swapping its first choice for the greedy's without increasing cost, the exchange argument is a sufficient proof.

Steps 4: Because after fixing the first choice the remainder is a smaller instance of the same problem, optimal substructure lets the argument repeat by induction.

Steps 5: Prove the safe choice and the remaining subproblem for the chosen rule. If that proof fails, revise the rule or explore another algorithm; a failed attempt is not an impossibility theorem.

Steps 6: A disagreement with brute force is a concrete counterexample to this implementation or rule. Agreement on all tested inputs is bounded evidence, not a prediction that an exchange argument must exist.

Picture: Walking through a hedge maze with no map, choosing at each junction the path that looks most open. Sometimes the maze is built so that the open-looking path is always the right one, and you walk straight to the exit. Sometimes it is built so the widest corridor is a trap. You cannot tell which maze you are in by looking at the first junction — you have to reason about how the maze was constructed.

Trigger: Fires when a problem asks for a minimum or maximum count, an obvious local rule presents itself, and n is too large for a quadratic DP.

Name: Greedy

Gain: Usually O(n) or O(n log n); very short code; low memory; often the only approach fast enough when n is 10^5 or more

Cost: Correctness is not self-evident and requires a proof; a wrong rule produces plausible output and fails on inputs you would not think to try

Name: Dynamic programming

Gain: A well-defined state and complete recurrence can represent interacting choices; prove base cases, transitions, evaluation order and reconstruction if required.

Cost: Time equals the number of reachable states times the work per state, and memory depends on retained states. Either can be linear, polynomial or exponential; DP has no universal quadratic minimum.

Pick: Use greedy when the stated rule has a correctness argument for the actual domain. Use bounded brute-force comparisons to search for counterexamples and validate implementation details. A failing candidate may lead to a better greedy, as with Jump Game II, or to DP or search.

Complexity

Greedy solutions are typically O(n) or O(n log n) — a single pass, or a sort followed by a single pass. These are the bounds of these examples, not a conclusion forced by ruling out a quadratic algorithm.

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 + A) time, O(A) space for the frequency formula above, where N is the number of tasks and A the distinct labels; with a fixed 26-letter alphabet this is O(N) time and O(1) auxiliary space. A tick-by-tick heap simulation must also count idle slots, so it can depend on the output schedule length L rather than just N. Event-jumping simulation can skip long idle stretches.

Partition Labels: O(n) time, O(A) auxiliary space, plus O(p) output for p partitions. With a fixed alphabet, A is constant; arbitrary strings can have A up to n.

These examples achieve linear scans once their decision rules are proved. DP also needs a proof, and the actual speed difference depends on the competing implementation; asymptotic analysis is not a measured tenfold gain.

Quiz

Self-check (answer follows each question).

Q: State the exchange argument in your own words.

A: Take any optimal solution. Show that modifying it so its first choice matches the greedy's first choice never makes it worse. Since the modified solution is still optimal and now agrees with the greedy, induction on the remaining subproblem shows the greedy is optimal overall.

Q: Why does 'always jump as far as possible' fail on Jump Game II?

A: It maximises the wrong quantity. On [2,3,1,1,4] jumping furthest lands on index 2, which reaches only one step further, taking three jumps. Landing on index 1 travels less but reaches index 4 directly, taking two. You must maximise reach after the jump, not jump length.

Q: What two properties must hold for a greedy algorithm to be correct?

A: The greedy choice property — some optimal solution contains the greedy's first choice — and optimal substructure, meaning the remaining problem after that choice is a smaller instance of the same problem.

Q: In Gas Station, why can you skip every station between the failed start and the point where the tank went negative?

A: Every prefix from the current start up to just before the failure had non-negative running total, so any later start in that window begins with no more accumulated surplus than the current start had. Since the current start failed, those must fail too.

Q: What constraint size hints that greedy rather than DP is intended?

A: Large n may rule out the obvious quadratic DP under the actual operation and runtime limits. It does not imply a linear algorithm or greedy; optimized DP or O(n log n) methods may also fit.

Q: Describe a cheap, reliable way to test a greedy rule before committing to it.

A: Enumerate feasible solutions on small bounded inputs and compare the optimum with the candidate. A mismatch refutes it on that input. Agreement establishes only the tested domain; follow with a proof for arbitrary allowed inputs.

Stretch: true

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 prefix-sum elimination argument 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, sketch a heap simulation, accounting for executed tasks and idle handling rather than assuming runtime depends only on task count.
• 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 a correctness argument out loud: BFS layers, prefix sums, forced boundaries, or a scheduling bound. 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. Correctness 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

These are practice selections, not verified company-frequency evidence.

• Jump Game II (45) — Medium · the reach-vs-length correction.
• Gas Station (134) — Medium · the proof-heavy one.
• Task Scheduler (621) — Medium · formula vs. heap simulation.
• Partition Labels (763) — Medium · forced-rule greedy.
• Jump Game (55) — Medium · the feasibility sibling; reject an index beyond the reachable frontier, but accept an already-reached last index.
• 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 · a useful two-pass greedy; more involved one-pass slope-counting solutions also exist.

Recovery scripts

Blanking mid-review 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 reviewers 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 this rule. Let me check whether another choice has a provable invariant; otherwise I will define a DP or search state."

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

If a reviewer 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 a reviewer 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.

You can now…

• State any greedy rule in a single sentence before writing code.

• Run a disciplined two-minute counter-example hunt on three- and four-element inputs.

• Give the exchange argument out loud in three sentences, unprompted.

• Explain why 'jump furthest' fails on [2,3,1,1,4] and what quantity to maximise instead.

• Prove the Gas Station restart rule rather than asserting it.

• Use large n to question a quadratic implementation, without mistaking a complexity constraint for a correctness proof.

• Verify a greedy against brute force over all inputs up to length six in about ten lines.

• Recover verbally when you blank, using a structured script instead of silence.

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.

• State the rule in one sentence, then spend two minutes trying to break it with a four-element input. Do this before writing any code.

• For an exchange-and-induction proof, establish a safe greedy choice and the remaining subproblem; failure of one candidate does not force DP.

• The exchange argument is the proof technique — swap an optimal solution's first choice for the greedy's and show nothing is lost.

• When a greedy fails, ask what quantity you should have maximised instead. Jump Game II maximises reach after the jump, not jump length.

• Large n can rule out a particular quadratic implementation, not the entire DP family.

• Passing tests is bounded evidence. Compare with an independent oracle, then prove the rule for the full contract.

Corrective source notes

• Introduction to Dynamic Programming - Algorithms for Competitive Programming — Memoization stores subproblem results so repeated states need not be recomputed. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.