leetExpert

Module 22 · Greedy

Practice

Practice~2 min

How to practice this module

Greedy drills reward the proof, not the guess: name the invariant the greedy choice maintains. Jump games track reach, gas-station uses a net surplus tour, partition-labels closes intervals, candy distributes with two sweeps. Done when all five show Solved in the hub.

Problems

Greedy — work them in order; difficulty ascends.

0/5

solved

  1. 1Jump GameMediumRunning reachWatch for: Track the farthest reachable index; if i ever passes it, the end is unreachable — greedy on reach, not on individual jumps
  2. 2Jump Game IIMediumJump frontierWatch for: Count jumps per reach frontier; greedily maximise reach each step — the off-by-one on the final jump is the classic bug
  3. 3Gas StationMediumNet surplus tourWatch for: If total gas < total cost there is no answer; start just after the point where the running surplus went most negative
  4. 4Partition LabelsMediumLast-occurrence windowsWatch for: Extend the current partition's end to the last occurrence of each letter inside it; close only when i reaches that end
  5. 5CandyHardTwo-sweep ratingsWatch for: Pass left-to-right then right-to-left; a peak child gets max(left, right) + 1 — a single pass misses one side

Cheatsheet

Greedy — Local choice with a proof sketch — sort first, then commit.

Smell → pattern

  • Activity selection / jumpsEarliest end / farthest reach
  • Assign resources optimallySort both sides
  • Huffman-like combineAlways merge smallest

Patterns

Sort by key, then take

Core

Smell: Activity selection / interval scheduling

Pick the ordering that makes the greedy choice obvious (earliest end, largest value…). Prove no better swap exists.

pick527

Running reach

Safe

Smell: Jump Game / farthest index

Track the farthest index reachable so far; fail if i passes it. The invariant is ‘everything ≤ reach is attainable’.

write region

Exchange argument mindset

Reach

Smell: Need a proof sketch, not vibes

If an optimal solution differs, show you can swap toward your greedy pick without hurting the objective.

pick527

Complexity targets

  • Sort + linear greedy

    Time
    O(n log n)
    Space
    O(1)*
    Note
    *or O(n) for output

  • Heap greedy

    Time
    O(n log n)
    Space
    O(n)
    Note
    Repeated extract-min

Traps

  • Greedy without monotonicity

    If a local improvement can block a better global, greedy fails — switch to DP or search.

  • Wrong sort key

    Sorting by start when the proof needs earliest end (or vice versa) is a silent wrong answer that ‘looks sorted’.