Greedy Algorithms

The mental model: burn bridges behind you

Greedy algorithms work when the future doesn't punish you for being locally optimal. More precisely: when there exists an ordering of choices such that the best pick right now is always part of some globally optimal solution. That is the greedy-choice property.

If you have it, you can prune your decision space at each step — choose, commit, forget. The algorithm walks forward once and never revisits. This is what makes greedy problems feel clean: you're not maintaining state across subproblems or filling a table. You're just scanning.

The moment you suspect an early commitment could block a cheaper path later, greedy is off the table. That's the boundary where dynamic programming takes over — it keeps all paths alive until there's enough information to choose.

When greedy is correct: the exchange argument

This is the intuition you need to carry out of this article. Suppose a genie gives you an optimal solution. Now compare it to what your greedy algorithm would have chosen at step 1. If the greedy pick is different, can you swap the genie's step-1 choice for the greedy one without making the solution worse?

If yes, repeat for step 2. And step 3. If you can always do this swap — the proof people call the exchange argument — then the greedy solution is optimal. Not close to optimal. Optimal.

In interviews you won't write the formal proof, but you should be able to articulate it verbally: "If I pick anything other than the earliest-finishing activity, I can swap it for the earliest-finishing one and end up with at least as many activities, because the earliest-finishing one conflicts with the fewest future choices." That's the exchange argument for activity selection, in one sentence.

The tell: what signals a greedy problem

These show up together often enough to be reliable:

• Optimize a count or total (maximize activities, minimize coins, maximize coverage).
• A natural ordering exists — if you sort by one attribute (end time, size, value/weight ratio), the greedy order becomes obvious.
• Each choice affects remaining options in a simple, monotonic way — picking the thing that "wastes least future space" is always safe.
• The optimal substructure is trivial — once you make a greedy choice, the remaining problem is the same problem on a smaller input.

The counter-signal: arbitrary weights or values on items. The moment items have both a cost and a value and you're trying to pack a knapsack, the greedy ratio trick (fractional knapsack) breaks down for the 0/1 variant. Weights and values that interact in non-monotonic ways almost always require DP.

Pattern: sort then scan

Most greedy algorithms have this skeleton:

def greedy_template(items):
    # 1. Sort by the attribute that defines the greedy order
    items.sort(key=lambda x: x.end_time)   # or size, value/weight, etc.

    result = []
    state = initial_state()

    # 2. Scan once, committing greedily
    for item in items:
        if compatible(item, state):
            result.append(item)
            state = update(state, item)

    return result

The art is figuring out the right key for sort and the right definition of compatible. The rest is mechanical.

Worked example 1: Activity Selection (Interval Scheduling)

Problem: Given n activities each with a [start, end] time, find the maximum number of non-overlapping activities.

The wrong instinct: pick shortest duration first. Counter-example: [1,10], [2,3], [4,5]. Shortest-first picks [2,3] and [4,5] — correct here by luck. But it doesn't generalize.

The right rule: sort by end time, always pick the activity that finishes earliest.

Why it works (exchange argument): suppose an optimal solution starts with activity X but greedy would start with activity Y (earliest end time). Since Y ends no later than X, any activity that's compatible with X is also compatible with Y. Swapping X for Y in the optimal solution can't shrink the count. Repeat this argument for every position.

def activity_selection(activities):
    # activities: list of [start, end]
    activities.sort(key=lambda x: x[1])   # sort by end time

    selected = []
    last_end = -1

    for start, end in activities:
        if start >= last_end:              # no overlap with last selected
            selected.append([start, end])
            last_end = end

    return selected

# Example
acts = [[1,4],[3,5],[0,6],[5,7],[3,9],[5,9],[6,10],[8,11],[8,12],[2,14],[12,16]]
print(activity_selection(acts))
# → [[1,4],[5,7],[8,11],[12,16]] — four activities, provably maximum

Time: O(n log n) for sort, O(n) for the scan. This is the canonical greedy problem. Internalize it; the variants (meeting rooms II, minimum number of platforms) all trace back to this shape. See interval techniques for a full treatment of the interval family.

Worked example 2: Jump Game

Problem (LeetCode 55): You're at index 0 of an array where nums[i] is the maximum jump length from index i. Determine if you can reach the last index.

The brute force trap: DP — let dp[i] be True if you can reach index i. Transition: dp[i] = any(dp[j] for j in range(i) if j + nums[j] >= i). O(n²). This works but it's doing too much thinking.

The greedy insight: track the farthest index you can currently reach. As you scan left to right, if you ever step past that frontier, you're stuck.

{ "type": "array", "title": "jump game — track max reachable index", "data": [2, 3, 1, 1, 4] }

Pick any element. Its value is how far you can jump from there. The question is whether your "reachable frontier" ever extends to or past the last index.

def can_jump(nums):
    max_reach = 0

    for i, jump in enumerate(nums):
        if i > max_reach:           # we can't reach this index
            return False
        max_reach = max(max_reach, i + jump)   # extend frontier

    return True   # we made it through without getting stuck

# Examples
print(can_jump([2,3,1,1,4]))   # True
print(can_jump([3,2,1,0,4]))   # False — frontier stalls at index 3

One pass, O(n), O(1) space. The greedy choice is "always maximize how far I can reach from any position I can stand on." You don't need to track which jumps you took — just whether you can keep the frontier advancing.

The harder variant (Jump Game II: minimum number of jumps) extends this with a second tracked variable for the current "level" end — same O(n) greedy, slightly more state.

Worked example 3: Gas Station

Problem (LeetCode 134): N gas stations in a circle. gas[i] is how much gas you get at station i, cost[i] is what it costs to drive to station i+1. Find the starting station that lets you complete a full circuit, or return -1.

This one is worth pausing on because the greedy argument is less obvious.

Key observations:

1. If sum(gas) < sum(cost), it's impossible — no starting point helps.
2. If a solution exists, it's unique.
3. If you simulate starting at index 0 and your tank ever goes negative at index k, then no station between 0 and k can be the valid start (if starting from 0 fails by station k, starting from any intermediate point hits station k with even less gas than we had when starting from 0).

def can_complete_circuit(gas, cost):
    total_tank = 0
    current_tank = 0
    start = 0

    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total_tank += gain
        current_tank += gain

        if current_tank < 0:
            # can't reach i+1 from 'start'; reset
            start = i + 1
            current_tank = 0

    return start if total_tank >= 0 else -1

One pass, O(n). The greedy choice is: as soon as the cumulative tank drops below zero, give up on every candidate we've seen so far and reset to the next station. The total_tank check at the end validates that a solution exists at all.

Worked example 4: Assign Cookies

Problem (LeetCode 455): You're a generous parent. Each child has a greed factor g[i]; each cookie has a size s[j]. Cookie j satisfies child i if s[j] >= g[i]. Maximize the number of satisfied children.

The greedy rule here almost writes itself: sort both arrays. For each cookie starting from the smallest, try to satisfy the least-greedy unsatisfied child. If the cookie is big enough, satisfy them and move on to the next child.

def find_content_children(g, s):
    g.sort()   # children by greed, ascending
    s.sort()   # cookies by size, ascending

    child = 0
    for cookie in s:
        if child < len(g) and cookie >= g[child]:
            child += 1   # this child is satisfied; move to next
    return child

O(n log n) for sort. The exchange argument: if a larger cookie could satisfy this child, swapping in the smaller one (which also satisfies them) saves the larger cookie for a greedier child. You never waste big cookies on easy children.

The greedy vs. DP decision

This decision is worth getting comfortable with because interviews test it constantly.

flowchart TD
    A["Does the problem ask for optimizing\na sum, count, or sequence?"] --> B
    B{"Can you define a natural\nordering of choices?"}
    B -->|yes| C{"Does an early greedy commit\never block a cheaper future path?"}
    B -->|no| DP["Dynamic Programming\nor other approach"]
    C -->|no — exchange argument holds| G["Greedy ✓\nSort + scan, O(n log n)"]
    C -->|yes / unsure| DP["Dynamic Programming\nO(n²) or O(n·k)"]
    DP --> E["Check: overlapping subproblems?\nOptimal substructure?"]

    style G fill:#00ff9d,color:#0a0a0f
    style DP fill:#7c5cff,color:#fff

The critical test: coin change. With denominations [1, 5, 10, 25] (US coins), greedy (largest first) always works. With denominations [1, 3, 4] and target 6, greedy picks 4 + 1 + 1 = 3 coins. Optimal is 3 + 3 = 2 coins. Greedy fails because 4 is locally tempting but globally blocking. The moment your coin system has "awkward" denominations, you need DP.

Problem	Greedy?	Why
Activity selection (maximize count)	Yes	Exchange argument: earliest-end is always swappable in
Fractional knapsack	Yes	Take highest value/weight ratio; fractions make this lossless
0/1 knapsack	No	Can't take fractions; early commit blocks optimal subset
Coin change (canonical denominations)	Sometimes	Only works when each denomination divides the next
Coin change (arbitrary denominations)	No	Classic DP problem
Jump Game (can you reach end?)	Yes	Maximizing frontier never hurts
Shortest path, non-negative weights	Yes	Dijkstra's is greedy
Shortest path, negative weights	No	Bellman-Ford required
Huffman coding	Yes	Provably optimal, exchange argument applies

One more heuristic that works surprisingly often: if the problem has O(n) or O(n log n) as the expected complexity in the discussion, it's probably greedy. If the expected complexity is O(n²) or involves two nested states, it's probably DP.

Common mistakes and pitfalls

Sorting by the wrong attribute. Activity selection: sort by end time, not start time and not duration. Sorting by start time gives a completely wrong answer. Sorting by duration is also wrong (try [1,10],[2,3],[4,5] — wait, this actually works here, which is exactly why it fools people. Try [1,100],[2,50],[51,100] — duration-first picks the [2,50] and [51,100] tie at 49 each; end-time-first picks [1,100] and then nothing, wait — let me be honest: this is a class of bugs that bites you on specific inputs, not always on your examples.) Write the exchange argument, don't just test on your two examples.

Assuming greedy is O(1) space. Many greedy algorithms are O(1) extra space, but not all. When you sort the input, that may be O(n) depending on the language's sort stability guarantees and whether you're sorting in-place or making a copy.

Greedy for scheduling with weights. Weighted job scheduling (each job has a profit) is not solvable by greedy; it needs DP or segment trees. This surprises people who solved the unweighted version greedily and assume the same approach extends. The weight is the wrench. See dynamic programming for the weighted variant.

Confusing "locally optimal" with "arbitrary." Greedy is not "just guess." It is a provably optimal local choice at each step. If you can't state why your local choice is the right one — if it's just intuition — go back and check with an exchange argument or a small counter-example before coding.

Off-by-one on interval compatibility. The condition for non-overlap is start >= last_end, not start > last_end. Whether endpoints are inclusive or exclusive matters. The problem statement usually tells you; read it.

When NOT to use greedy

Use something else when:

• Items have both a cost and a value and you're choosing a subset (knapsack). The value/weight ratio heuristic works only for the fractional version.
• The graph has negative edge weights (Dijkstra's greedy assumption breaks; use Bellman-Ford or SPFA).
• You need the globally optimal path through a state space where early choices can invalidate later ones — this is DP territory.
• The problem has "minimum cost to achieve X" with arbitrary cost structure — again, probably DP. See dynamic programming for the DP versions of problems that look greedy but aren't.
• You need a sorted output. Greedy is about picking, not ordering. If you need sorting as a sub-step, that's fine, but if sorting is the actual goal, look at the comparison-sort algorithms directly.

The failure mode is the worst kind: greedy gives a plausible, slightly suboptimal answer with no indication it's wrong. Dynamic programming gives the actual optimum. Know the boundary.

The one question to ask yourself

Before committing to greedy on any problem, ask: "Is there a situation where the greedy choice now makes the global answer worse?"

If you can construct a concrete counter-example in two minutes, don't use greedy. If you can sketch an exchange argument — "whatever optimal did at step k, I can replace it with the greedy choice and not lose anything" — greedy is likely safe.

Greedy is powerful not because it's clever but because it's right. When it's correct, it's also the fastest algorithm you could possibly write. That combination — provably optimal and O(n log n) — is what makes activity selection and its cousins the clean, satisfying problems they are.