L49 · Greedy — And Proving It Works

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

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.

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.