Greedy · Lyte Code

Take the locally optimal choice and never reconsider — when that yields the global optimum, the proof techniques that justify it, and the classic greedies.

The idea

A greedy algorithm builds the answer by always taking the best-looking choice right now, never backtracking. It’s simple and fast (often one pass after a sort), but only correct when local optimality implies global optimality. The hard part isn’t coding it — it’s knowing (and proving) that greedy is valid here rather than DP.

When greedy works

Two properties must hold:

Greedy-choice property — a globally optimal solution can be reached by making the locally optimal choice at each step.
Optimal substructure — an optimal solution contains optimal solutions to subproblems.

If a greedy choice can paint you into a corner (a locally great move that forecloses the true optimum), it’s a DP problem instead. When unsure, hunt for a counterexample — one breaks greedy; failing to find one (plus a proof) supports it.

Proving a greedy (the part interviewers probe)

Exchange argument — take any optimal solution and show you can swap its choices for the greedy ones, one at a time, without making it worse → greedy is at least as good.
“Greedy stays ahead” — show that after each step, the greedy partial solution is at least as good as any other on the relevant measure.
Matroid theory — the formal umbrella for why many greedies (spanning trees, scheduling) are optimal; name-drop only if relevant.

Worked examples

Jump game — track the furthest reachable index; if you fall behind it, you’re stuck:

def can_jump(nums):
    reach = 0
    for i, n in enumerate(nums):
        if i > reach: return False
        reach = max(reach, i + n)
    return True

Interval scheduling — sort by end time, take each interval starting after the last taken ends (earliest-finish is provably optimal — exchange argument). See the intervals primer.

Kadane (max subarray) — drop the running sum the moment it goes negative (a greedy reset).

The classic greedies (recognize them)

Activity / interval selection — earliest finish time.
Fractional knapsack — highest value/weight ratio first (the 0/1 knapsack is DP, not greedy — a classic trap).
Huffman coding — repeatedly merge the two least-frequent nodes (a heap-driven greedy).
Dijkstra / Prim — always expand the nearest/cheapest frontier node (greedy + heap; see advanced graphs).
Jump Game II — fewest jumps via a BFS-like furthest-reach greedy.
Gas Station — if total gas ≥ total cost, the start is just after the lowest running deficit.
Task Scheduler, Hand of Straights, Partition Labels, Candy, Assign Cookies, Merge/Remove for monotonic — sort or count, then sweep.

Greedy vs DP (the boundary)

	Greedy	DP
Choice	commit, never revisit	try all, keep the best
Speed	O(n) / O(n log n)	often O(n·states)
Valid when	greedy-choice property holds	overlapping subproblems, choices interact
Example	fractional knapsack, intervals	0/1 knapsack, edit distance

If choices interact (taking one changes the value of others in non-local ways), reach for DP.

Pitfalls

Assuming greedy without proof — many “obvious” greedies are wrong (0/1 knapsack, coin change with arbitrary denominations).
Wrong sort key — the whole correctness often hinges on sorting by the right field (end time, ratio, deadline).
Edge cases — empty input, ties, all-equal elements.

Choosing in an interview

State your greedy rule, then immediately justify it (“sort by end time; by an exchange argument, picking the earliest-finishing interval never hurts”) or find a counterexample and switch to DP. The justification — not the code — is what’s being tested.