Take the locally optimal choice at each step and prove it stays globally optimal: interval scheduling, jump game, Huffman coding — and how to know when greedy is even valid.
0 of 6 lessons checked off
Introduction
What it is
A greedy algorithm builds a solution by repeatedly making the choice that looks best right now — the locally optimal move — and never reconsidering it.
The catch: greedy is only CORRECT when local optimality provably forces global optimality. Half the topic is recognising when that holds and when it's a trap.
Why it matters
When greedy works it's the simplest and fastest tool — usually O(n log n) after a sort, versus DP's O(n²) or exponential search.
Interviewers test judgement: many candidates apply greedy where it fails (coin change with arbitrary denominations, 0/1 knapsack). Knowing the difference is the skill being graded.
How it works
Two properties must hold: the GREEDY-CHOICE PROPERTY (a locally optimal choice is part of some global optimum) and OPTIMAL SUBSTRUCTURE (an optimal solution contains optimal solutions to subproblems).
Prove correctness with an EXCHANGE ARGUMENT: assume an optimal solution differs from the greedy one, then show you can swap in the greedy choice without making it worse — so greedy is at least as good.
In practice: sort by the right key (finish time, ratio, deadline), then sweep making the obvious pick and discarding conflicts.
Where it's used
Huffman compression (used in ZIP/JPEG), CPU/task scheduling by deadline, bandwidth allocation, cache eviction heuristics, and Dijkstra/Prim/Kruskal (all greedy at heart).
Analogy: Making change as a cashier with standard coins: always hand over the largest coin that fits. For US/EU coins this greedy rule is provably optimal — but for a contrived coin set like {1, 3, 4}, it fails (6 = 4+1+1 greedily, but 3+3 is better). Same instinct, one works, one doesn't — which is the whole lesson.
Interactive diagram
Sorting by earliest finish and greedily taking non-conflicting meetings maximises the count — provably.
[1,3]0
[2,4]1
[3,5]2
[5,7]3
[6,8]4
[8,9]5
Sort by finish time
Six meetings sorted by when they END. Finishing early leaves the most room for others — the greedy key.
1 / 6
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
When is greedy valid?
Greedy-choice property + optimal substructure; the coin-change cautionary tale.
25 min
Exchange arguments (proofs)
Proving greedy correct by swapping toward the greedy choice.
25 min
Interval scheduling & selection
Sort by finish time; the archetypal correct greedy.
30 min
Jump game & gas station
Reachability frontiers and running-deficit tricks.
25 min
Huffman coding
Merge the two least-frequent nodes repeatedly (a heap-driven greedy).
25 min
Greedy vs dynamic programming
Fractional (greedy) vs 0/1 (DP) knapsack — the dividing line.
25 min
Operations
Interval scheduling (max non-overlapping)
Sort by finish time; greedily take each interval that starts at or after the last taken finish. Earliest finish = maximum room left.
Interval scheduling (max non-overlapping)
1defmax_meetings(intervals:list[tuple[int,int]])->int:2"""Maximum number of non-overlapping intervals. O(n log n)."""3intervals.sort(key=lambdaiv:iv[1])# by FINISH time — the key insight4count=05last_end=float("-inf")6forstart,endinintervals:7ifstart>=last_end:# no conflict8count+=19last_end=end# advance the frontier10returncount
Time: O(n log n) (dominated by the sort)Space: O(1) beyond the sort
Edge cases
Sort by FINISH, not start — sorting by start is the classic wrong greedy.
Touching intervals ([1,3] and [3,5]): decide if endpoints count as overlap (>= vs >).
Empty input → 0.
Common mistakes
Sorting by start time or by duration — both give suboptimal counts on adversarial inputs.
Not proving (even informally) why earliest-finish is safe when asked.
Jump game (reachability frontier)
Track the farthest index reachable so far; if you ever stand beyond it, you're stuck. No DP needed.
Jump game (reachability frontier)
1defcan_jump(nums:list[int])->bool:2"""Can you reach the last index? nums[i] = max jump from i. O(n)/O(1)."""3farthest=04fori,jumpinenumerate(nums):5ifi>farthest:# a gap we can't cross6returnFalse7farthest=max(farthest,i+jump)# extend the frontier greedily8iffarthest>=len(nums)-1:9returnTrue10returnTrue
Time: O(n)Space: O(1)
Edge cases
Single element: already at the end → True.
A 0 is only fatal if the frontier can't already reach past it.
Early return once the end is reachable saves the rest of the scan.
Common mistakes
Writing an O(n²) DP when the greedy frontier is O(n).
Checking reachability only at the end instead of at each index.
Huffman coding (heap-driven greedy)
Repeatedly merge the two least-frequent nodes into a parent; rarer symbols end up deeper (longer codes). Optimal prefix-free encoding.
Huffman coding (heap-driven greedy)
1importheapq234defhuffman_code_lengths(freqs:dict[str,int])->dict[str,int]:5"""Optimal prefix-code length per symbol. O(n log n)."""6iflen(freqs)==1:# single symbol: 1-bit code7return{sym:1forsyminfreqs}89# heap of (frequency, tie-breaker, node); node = symbol or merged subtree10counter=011heap:list=[(f,i,s)fori,(s,f)inenumerate(freqs.items())]12counter=len(heap)13heapq.heapify(heap)1415depth:dict[str,int]={s:0forsinfreqs}1617whilelen(heap)>1:18f1,_,a=heapq.heappop(heap)# two rarest nodes
Time: O(n log n)Space: O(n)
Edge cases
Single symbol needs a special case (1 bit, not 0).
Ties broken by an incrementing counter so tuples never compare raw subtrees.
Comparing nodes directly in the heap (crashes on ties) — always carry a tie-breaker.
Assuming greedy-merge is arbitrary; it's provably optimal (Huffman's theorem).
Complexity analysis
Operation
Best
Average
Worst
Space
Interval scheduling
O(n log n)
O(n log n)
O(n log n)
O(1)
Jump game / gas station
O(n)
O(n)
O(n)
O(1)
Huffman coding
O(n log n)
O(n log n)
O(n log n)
O(n)
Fractional knapsack
O(n log n)
O(n log n)
O(n log n)
O(1)
0/1 knapsack (greedy FAILS)
—
—
—
—
The last row is the point: greedy gives a WRONG answer for 0/1 knapsack — that one needs DP. Speed means nothing if the answer is incorrect.
Python implementation
Production-quality code with type hints, validation, and docstrings.
Fractional vs 0/1 knapsack — the greedy dividing line
1deffractional_knapsack(items:list[tuple[int,int]],capacity:int)->float:2"""items=[(value,weight)].YouMAYtakefractionsofanitem.3Greedybyvalue/weightratioisOPTIMALhere.O(nlogn)."""4items.sort(key=lambdait:it[0]/it[1],reverse=True)# best ratio first5total=0.06forvalue,weightinitems:7ifcapacity>=weight:8total+=value# take the whole item9capacity-=weight10else:11total+=value*(capacity/weight)# take the fraction that fits12break# knapsack is now full13returntotal141516defzero_one_knapsack(items:list[tuple[int,int]],capacity:int)->int:17"""items=[(value,weight)].Eachitemisall-or-nothing.18GreedyFAILS;thisneedsDP.O(n·capacity)."""
What interviewers expect you to know
The judgement being tested
Before coding greedy, ASK: does a locally optimal choice provably stay globally optimal? If you can't argue it, greedy may be wrong.
The two pillars: greedy-choice property and optimal substructure. Name them.
Know the famous failures: coin change with arbitrary denominations, 0/1 knapsack, longest path — all need DP.
Proving greedy correct
Exchange argument: take any optimal solution, show you can swap its first differing choice for the greedy one without loss. Repeat → greedy is optimal.
'Stays ahead': show greedy's partial solution is never worse than any other after each step (interval scheduling).
Choosing the sort key
Interval count → finish time. Interval merging → start time. Knapsack (fractional) → value/weight ratio. Job sequencing → profit then deadline. The key IS the algorithm.
State the key and WHY out loud — 'sort by finish so each pick leaves maximum room' — before writing the loop.
Common mistakes
Applying greedy where it fails
0/1 knapsack, arbitrary-coin change, and longest simple path all look greedy-friendly and aren't. If you can't prove the greedy-choice property, suspect DP.
Wrong sort key
Interval scheduling by START time or by DURATION gives suboptimal counts. The correct key (finish time) is the crux — get it wrong and everything downstream is wrong.
No correctness argument
Greedy that happens to pass the examples but has no exchange argument is fragile. Interviewers ask 'why is this optimal?' — have the one-line answer ready.
Reconsidering choices
True greedy never backtracks. If your solution revisits earlier decisions, it's really DP or search wearing greedy's clothes.
Heap ties crashing
In Huffman/scheduling heaps, comparing composite objects fails on equal keys. Always include a unique tie-breaker in the tuple.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.
5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.
Frequently asked questions
How do I quickly tell if greedy will work?
Ask whether a locally optimal choice can ever block a better global outcome. If a small counterexample breaks it (like coins {1,3,4}), it's DP. If you can sketch an exchange argument, greedy is safe. When unsure in an interview, say 'greedy is tempting; let me check for a counterexample' — that judgement is what's graded.
Greedy vs DP — is greedy just faster DP?
When both apply, greedy is faster (no table). But greedy makes ONE choice and commits; DP considers ALL choices and keeps the best. Greedy needs the greedy-choice property; DP only needs optimal substructure. That extra requirement is exactly what greedy can lack.
Are Dijkstra and Prim greedy?
Yes — both repeatedly commit to the locally best option (closest node / cheapest crossing edge) and never revisit it. Their correctness rests on greedy-choice properties (non-negative weights / the cut property), which is why they belong to this family.
Summary & cheat sheet
Key takeaways
Greedy = commit to the local optimum, never reconsider — valid only with the greedy-choice property + optimal substructure.
Prove it with an exchange argument; disprove it with a small counterexample.
The sort key IS the algorithm: finish time (scheduling), ratio (fractional knapsack), deadline (jobs).
Famous failures needing DP: 0/1 knapsack, arbitrary-coin change, longest path.
When it works, greedy is the simplest and fastest correct tool.
Formulas & cheat sheet
Interval scheduling: sort by finish, take if start ≥ last_end
Fractional knapsack: sort by value/weight descending
Huffman: repeatedly merge the two smallest frequencies
Interview checklist
I check the greedy-choice property before committing to greedy.
I can give an exchange argument for a correct greedy.
I know coins {1,3,4} and 0/1 knapsack as greedy failures.