Greedy · Solvarch

Greedy = commit to the locally best choice and never look back. It's the fastest pattern when it works and confidently wrong when it doesn't — so in an interview, the algorithm is half the answer; the exchange argument ("swapping any other choice for mine never improves the result") is the other half.

Recognize it

"Maximum number of events you can attend / tasks you can finish."
"Minimum jumps/refuels/moves to reach the end."
Sorting one way makes each decision obvious and irreversible.
A DP formulation exists but the constraint sizes demand O(n log n).

Templates

# Reach/coverage greedy (Jump Game)
def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach: return False
        reach = max(reach, i + x)
    return True

# Level-up greedy (Jump Game II): expand a frontier like BFS
def min_jumps(nums):
    jumps = cur_end = far = 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == cur_end:          # must jump now
            jumps += 1
            cur_end = far
    return jumps

Canonical greedy arguments

Earliest deadline / earliest end first: keeps maximum room for the rest — interval scheduling (Non-overlapping Intervals, see Intervals).
Total ≥ 0 means a start exists, and failures skip whole prefixes: Gas Station — when the tank dips negative at i, no station ≤ i can be the start.
Serve the cheapest satisfiable demand: sort both sides — Assign Cookies, Boats to Save People (pair heaviest with lightest).
Spend big bills first: Lemonade Change — keep small denominations flexible.
Most frequent first with cooldown: Task Scheduler — the count formula or a heap.
Consume in sorted order: Hand of Straights — smallest card must start a straight.
Range of possibilities instead of decisions: track [lo, hi] of open parens — Valid Parenthesis String.

Classic problems

Jump Game / Jump Game II
Gas Station
Best Time to Buy and Sell Stock II — take every uphill
Partition Labels
Task Scheduler
Remove K Digits — greedy with a stack

Pitfalls

Asserting greedy without an argument — if you can't sketch why local ⇒ global, suspect DP.
Sorting by the wrong key: interval scheduling by start instead of end is the textbook failure.
Greedy on knapsack-style value problems is wrong (that's DP); greedy works for fractional knapsack only.
Test greedy against a brute force on small inputs when unsure — a 30-second mental check that catches most false greedies.

Templates

# Reach/coverage greedy (Jump Game) def can_jump(nums): reach = 0 for i, x in enumerate(nums): if i > reach: return False reach = max(reach, i + x) return True # Level-up greedy (Jump Game II): expand a frontier like BFS def min_jumps(nums): jumps = cur_end = far = 0 for i in range(len(nums) - 1): far = max(far, i + nums[i]) if i == cur_end: # must jump now jumps += 1 cur_end = far return jumps

Canonical greedy arguments

Earliest deadline / earliest end first: keeps maximum room for the rest — interval scheduling (Non-overlapping Intervals, see Intervals).

Total ≥ 0 means a start exists, and failures skip whole prefixes: Gas Station — when the tank dips negative at i, no station ≤ i can be the start.

Serve the cheapest satisfiable demand: sort both sides — Assign Cookies, Boats to Save People (pair heaviest with lightest).

Spend big bills first: Lemonade Change — keep small denominations flexible.

Most frequent first with cooldown: Task Scheduler — the count formula or a heap.

Consume in sorted order: Hand of Straights — smallest card must start a straight.

Range of possibilities instead of decisions: track [lo, hi] of open parens — Valid Parenthesis String.

Pitfalls

Asserting greedy without an argument — if you can't sketch why local ⇒ global, suspect DP.

Sorting by the wrong key: interval scheduling by start instead of end is the textbook failure.

Greedy on knapsack-style value problems is wrong (that's DP); greedy works for fractional knapsack only.

Test greedy against a brute force on small inputs when unsure — a 30-second mental check that catches most false greedies.