Greedy

When greedy works, exchange arguments, and the six common greedy shapes.

A greedy algorithm makes the locally best choice at each step and never revisits it. When greedy works, it gives the simplest and fastest solutions you'll write in an interview. The hard part is knowing when it works and being able to justify it.

When to consider greedy

The problem asks for a min or max count: fewest jumps, most intervals, minimum number of boats.
Sorting the input reveals an obvious order to process things in.
A choice made now never makes a future choice worse.

If a choice now can block a better option later, you probably need dynamic programming.

Justifying a greedy choice

Interviewers often ask, "How do you know greedy is correct?" Two standard arguments:

Exchange argument: take any optimal solution that differs from the greedy one. Swap its first differing choice for the greedy choice. The solution is no worse. Repeat until it matches the greedy solution.
Stays ahead: after every step, the greedy solution is at least as good as any other solution at the same step.

[!INTERVIEW] Test against a counterexample first Before committing, try to break your greedy rule with a small input. Coin change with coins [1, 3, 4] and amount 6: greedy picks 4+1+1 (three coins), but 3+3 needs only two. Saying "I checked a counterexample" is a strong signal, and it stops you from coding a wrong solution for 20 minutes.

Pattern 1: sort, then sweep

Interval scheduling (pick the most non-overlapping intervals): sort by end time, and always keep the interval that finishes first. It leaves the most room for the rest.

def max_non_overlapping(intervals):
    count, end = 0, float("-inf")
    for s, e in sorted(intervals, key=lambda iv: iv[1]):
        if s >= end:
            count, end = count + 1, e
    return count

Two-pointer pairing (boats that carry up to two people): sort, then pair the heaviest remaining person with the lightest if they fit together. Otherwise the heaviest goes alone.

Assign cookies: sort both lists and give each child the smallest cookie that satisfies them.

Pattern 2: track the farthest reach

def jump(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:          # must jump to keep going
            jumps += 1
            cur_end = farthest
    return jumps

This is effectively BFS over levels without the queue: each "level" is the range reachable with a given number of jumps.

Pattern 3: running balance

Gas station: if the total gas is at least the total cost, a solution exists. Scan the stations while keeping a running tank. Whenever it goes negative, no station from the current start up to here can work, so restart from the next station.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0
    return start

Pattern 4: two passes

Candy (each child with a higher rating than a neighbor gets more candy): one left-to-right pass enforces the left neighbor rule, and one right-to-left pass enforces the right neighbor rule, taking the maximum.

Pattern 5: greedy with a heap

When the "best next choice" changes as you go, keep the candidates in a heap:

Minimum cost to connect sticks: always merge the two smallest.
Task scheduler / reorganize string: always place the most frequent remaining task that's allowed.
Meeting rooms: reuse the room that frees up earliest.

Pattern 6: custom sort order

Largest number from a list of integers: sort by comparing a+b against b+a as strings. Queue reconstruction by height: sort tallest first, then insert each person at index k.

Greedy vs DP at a glance

[!TIP] Practice Jump Game · Jump Game II · Gas Station · Partition Labels · Non-overlapping Intervals · Boats to Save People · Candy · Task Scheduler · Largest Number