Greedy

TL;DR

A greedy algorithm makes the locally optimal choice at every step and never revisits it. No memo table, no recursion stack, no second guesses — you walk the input once (often after a sort) and emit the answer. When it’s correct, it’s the cheapest tool in the box: O(n) or O(n log n), O(1) extra space.

The catch is correctness. Most problems that look greedy aren’t — 0/1 knapsack is the famous trap. The hard work isn’t writing the code, it’s proving the greedy choice is safe: that committing to it at step i never forces a worse outcome later. The standard proof technique is an exchange argument — show that any optimal solution can be transformed into the greedy one piece by piece without losing value.

Most “minimum number of jumps”, “maximum reach”, “non-overlapping intervals”, “activity selection”, and “schedule N tasks” problems land here. If you find yourself reaching for DP and the subproblems don’t actually overlap, stop and check whether a sort + single pass solves it.

When to reach for it

Signals that greedy is probably the right move:

• The problem asks for “minimum number of …” or “maximum …” over a sequence of independent choices.
• An exchange argument is plausible: swapping any optimal choice for the greedy one doesn’t break the solution.
• There are no overlapping subproblems — you don’t need to remember past states to make the current choice.
• A natural sort order (by end time, by ratio, by deadline) makes the right choice obvious at each step.

Signals that it’s not greedy:

• Choices interact — picking item i changes the value of item j later. That’s DP territory (knapsack, edit distance, LIS).
• You need to explore all configurations to find the answer (N-queens, subset enumeration). That’s backtracking.
• The “greedy” choice is only correct sometimes and you can construct a counterexample on the back of a napkin. Trust the counterexample.

Flavor 1 — Jump Game / Jump Game II

nums[i] is the max jump length from index i. Can you reach the last index? (LC 55) And if so, in how few jumps? (LC 45) The greedy idea: track the farthest reachable index as you scan, and for LC 45, treat each “jump” as expanding the current reachable window to that farthest index.

def can_jump(nums: list[int]) -> bool:
    farthest = 0
    for i, step in enumerate(nums):
        if i > farthest:
            return False  # we never reached i
        farthest = max(farthest, i + step)
    return True

def min_jumps(nums: list[int]) -> int:
    jumps = 0
    current_end = 0   # right edge of the current jump's reach
    farthest = 0      # best index reachable from anywhere within current jump
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

Worked example. nums = [2, 3, 1, 1, 4] for min_jumps.

Loop stops at i = 3 (we don’t process the last index). Answer: 2 jumps. The greedy choice — “always extend reach as far as possible before committing the next jump” — is provably optimal because any solution that jumps earlier than necessary can be modified to jump at the latest possible moment without using more jumps.

Flavor 2 — Interval scheduling (LC 435)

Given intervals, remove the minimum number so the rest don’t overlap. The canonical greedy: sort by end time, then greedily keep the earliest-ending interval that doesn’t conflict with the last one kept.

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])   # sort by end
    kept_end = float("-inf")
    kept = 0
    for start, end in intervals:
        if start >= kept_end:
            kept += 1
            kept_end = end
    return len(intervals) - kept

Worked example. intervals = [[1,2],[2,3],[3,4],[1,3]].

After sorting by end: [[1,2],[2,3],[1,3],[3,4]].

Kept 3, total 4, so remove 4 − 3 = 1. Picking the earliest-ending interval first is what makes this work: it leaves the maximum room on the right for future intervals.

Flavor 3 — Gas Station (LC 134)

Circular route with gas[i] available at station i and cost[i] to get to station i+1. Find the unique starting station from which you can complete the loop, or return -1 if impossible.

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    if sum(gas) < sum(cost):
        return -1
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1   # any station up to i can't be the answer
            tank = 0
    return start

Trace. gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2].

Answer: start = 3. The greedy leap: if the tank goes negative at index i, no station from the current start through i can be a valid origin — each of them would also fail at or before i. So jump start to i + 1 and reset. One pass, O(n).

Why it works — the invariant

The unifying proof technique is the exchange argument: take any optimal solution OPT and show you can swap in the greedy choice without breaking optimality.

• Interval scheduling. Suppose OPT doesn’t pick the earliest-ending interval g. Replace OPT’s first interval with g. Since g ends no later than OPT’s first pick, every subsequent interval in OPT is still valid. Same count, still optimal — so g was a safe choice.
• Jump Game II. Any solution that lands at index j after k jumps can be converted into one that lands at the farthest reachable index after k jumps. The farther you land, the more options you have for jump k + 1, so the greedy never does worse.
• Gas Station. If you fail at i starting from s, then for any s' ∈ [s, i], partial sums from s' to i are even smaller than from s (you removed non-negative prefix). So none of them work either.

Write the exchange argument before you trust the algorithm. If you can’t, you probably have a counterexample hiding.

Complexity

• Time: O(n) for single-pass scans (Jump Game, Gas Station). O(n log n) when a sort is the price of admission (interval scheduling, Huffman).
• Space: O(1) extra. Greedy lives on a couple of running variables — no memo table, no recursion stack.

Common pitfalls

• “Looks greedy, isn’t.” 0/1 knapsack is the canonical trap: sorting by value/weight ratio gives the right answer for the fractional version but can be arbitrarily wrong for 0/1. Coin change with arbitrary denominations is another — [1, 3, 4] making 6 greedy gives 4 + 1 + 1 = 3 coins, optimal is 3 + 3 = 2. Always test against a brute force on small inputs before committing.
• Sorting by the wrong key. Interval scheduling sorts by end, not start; minimum-platforms sorts events by time then by departure-before- arrival. Pick the key the exchange argument actually proves.
• Missing the tiebreaker. When two items sort equal, the wrong tiebreaker silently breaks correctness. Deadline scheduling needs (deadline asc, profit desc) — flip the second and you’ll drop money.
• Off-by-one on the loop bound. Jump Game II loops to n - 2, not n - 1, because reaching the last index is the goal, not a place to spend another jump. One extra iteration adds a phantom jump.
• Currency confusion in Gas Station. sum(gas) >= sum(cost) is necessary and sufficient — once you’ve checked it, the single-pass start-pointer logic always finds a valid station. Skipping the global check makes you return a “start” that fails partway around.

Where you see this in production

• Linux CFS scheduler. The Completely Fair Scheduler picks the runnable task with the smallest vruntime next — a greedy choice indexed by a red-black tree. The exchange argument is fairness: serving the least-served task minimises max lag.
• Huffman coding in zlib / gzip. Building an optimal prefix code by repeatedly merging the two lowest-frequency nodes is the textbook greedy proof — and it’s what deflate runs on every gzip stream.
• Kruskal’s MST in network provisioning. Sort edges by weight, add the cheapest that doesn’t form a cycle. Used inside infra tools that build spanning trees over racks or data centres for redundancy planning.
• Nagle’s algorithm in TCP. Hold small writes until either the previous segment is acknowledged or a full MSS accumulates — a greedy “wait if it helps, send if it doesn’t” choice that reduces tinygram congestion without per-connection bookkeeping.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.