Notifications
Last 30 Days
No notifications
Last 30 Days
No notifications
A greedy algorithm makes the locally optimal choice at each step, hoping to find the global optimum.
| Problem | Greedy Strategy |
| Activity Selection | Pick earliest ending activity |
| Fractional Knapsack | Pick highest value/weight ratio |
| Huffman Coding | Merge two lowest frequencies |
| Job Sequencing | Schedule highest profit jobs first |
| Minimum Coins | Pick largest denomination first |
Greedy algorithms are the shortest, fastest, and most fragile family in your toolbox. The shape is always: "at each step, take the locally best option and never look back." When it works (Kruskal, Dijkstra, Huffman, activity selection), the code fits in 10 lines. When it doesn't (0/1 knapsack, longest path), it silently returns wrong answers. The skill isn't writing greedy — it's *recognising when greedy is provably optimal*.
A greedy algorithm makes a sequence of irrevocable choices. At each step, it picks the option that looks best by some local criterion, commits to it, and moves on. There is no backtracking, no DP table, no caching of subproblems.
Two properties must hold for greedy to be correct:
1. Greedy choice property — there's always a locally optimal choice that is part of *some* globally optimal solution. 2. Optimal substructure — the optimal solution to the whole problem contains optimal solutions to its subproblems.
Both must hold. If only (2) holds, you've got a DP problem, not a greedy one.
You owe 67 cents. Hand over a 50 (largest ≤ 67), then a 10 (largest ≤ 17), then 5, then 2, then… For US/EUR coin systems, this gives the optimal (fewest coins) answer. For arbitrary coin systems, it doesn't — example: coins {1, 3, 4}, target 6. Greedy gives 4+1+1 = 3 coins, but 3+3 = 2 coins is optimal. *Same algorithm, different inputs, different correctness.* That's greedy in a nutshell.
1. Assuming greedy works because it gave the right answer on one example. Always test edge cases. Better: prove it via exchange argument. 2. Confusing 0/1 knapsack with fractional knapsack. Greedy by value/weight ratio is provably optimal for fractional, provably wrong for 0/1 (see worked example below). 3. Picking the wrong sort key. Activity Selection sorts by end time, not start time. Job Scheduling by profit descending. Fractional Knapsack by value/weight. Pick wrong → wrong answer. 4. Ignoring tie-breaking rules. "Sort by end time" — what if two intervals end together? Usually pick by start time as tiebreaker. Test this. 5. Trying greedy on problems that need DP ("longest path", "subset-sum", "0/1 knapsack", "min number of coins for arbitrary denominations"). If a small counterexample breaks it, switch to DP. 6. Not handling the empty / single-element case. Greedy code often dies on n = 0 or n = 1. Add a guard.
Items with (weight, value): \(10, 60), (20, 100), (30, 120)\. Capacity = 50.
Sort by value/weight ratio: 60/10 = 6.0, 100/20 = 5.0, 120/30 = 4.0.
Greedy picks item 1 (weight 10, value 60), then item 2 (weight 20, value 100). Used weight = 30. Item 3 weighs 30 — won't fit. Total = 160.
Optimal: items 2 + 3 — weight 50, value 220.
Greedy loses 60 because it can't reconsider item 1 once committed. Result: 0/1 knapsack needs DP, not greedy. The same items with fractional knapsack would work (take all of item 1 = 60, all of item 2 = 100, then 20/30 of item 3 = 80 → total 240 — actually beats both 0/1 answers because fractional is a strictly easier problem).
The standard proof technique:
1. Assume an optimal solution \O\ differs from the greedy solution \G\.
2. Look at the first point where they diverge.
3. Show that *swapping* O's choice for G's choice at that point produces a solution at least as good.
4. By induction, G is also optimal.
Used to prove activity selection (the earliest-ending interval is always swappable in), Huffman codes, fractional knapsack, and many scheduling problems.
| Aspect | Greedy | Dynamic Programming |
| Decisions | one shot, irrevocable | considers all options |
| Subproblems | non-overlapping, sequential | many overlapping |
| Backtracking | never | implicit (table) |
| Speed | usually O(n log n) | O(n²), O(n³), … |
| Correctness proof | *required* — exchange argument or matroid | recurrence correctness suffices |
| Risk | wrong answer if greedy doesn't apply | always correct (if recurrence is right) |
Default to DP when in doubt. Switch to greedy only when you can prove it.
Pick max number of non-overlapping intervals.
`js
function activitySelection(activities) {
activities.sort((a, b) => a[1] - b[1]); // sort by END time
const selected = [activities[0]];
let lastEnd = activities[0][1];
for (let i = 1; i < activities.length; i++) {
if (activities[i][0] >= lastEnd) {
selected.push(activities[i]);
lastEnd = activities[i][1];
}
}
return selected;
}
`
Why end-time sort works: the earliest-ending activity leaves the maximum room for future activities. Exchange argument: any other first choice ends no earlier, so it can't allow more activities afterward. Variant: weighted interval scheduling needs DP — greedy by end time fails.
`js
function fractionalKnapsack(items, W) {
items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let value = 0, capacity = W;
for (const it of items) {
if (capacity >= it.weight) { value += it.value; capacity -= it.weight; }
else { value += it.value * (capacity / it.weight); break; }
}
return value;
}
`
Why ratio sort works: value per unit weight is the "rate" — taking the highest rate first maximises value extracted per unit of capacity used.
Optimal prefix-free code where most-frequent characters get the shortest codes.
`
1. Build a min-heap keyed by frequency.
2. While heap.size > 1:
a = heap.pop(); b = heap.pop();
heap.push({ freq: a.freq + b.freq, left: a, right: b });
3. The remaining node is the root of the Huffman tree.
`
Complexity: O(n log n). Used in DEFLATE (zip, gzip, PNG), JPEG, MP3.
| Problem | Greedy strategy | ||||
| Job sequencing with deadlines | Sort by profit desc, place each in latest available slot ≤ deadline | ||||
| Min number of platforms | Sort arrivals + departures, sweep with two pointers | ||||
| Meeting rooms II | Min-heap of end times; pop if next start ≥ heap-top | ||||
| Jump Game | Track \maxReach\; if \i > maxReach\ you're stuck | ||||
| Jump Game II (min jumps) | Track current-jump-reach and next-jump-reach; bump count when crossing | ||||
| Gas station circular | If \sum(gas) ≥ sum(cost)\, the answer exists. Start from index where running balance is lowest | ||||
| Container with most water | Two pointers, move the shorter wall inward | ||||
| Assign Cookies | Sort both arrays, two-pointer match | ||||
| Boats to Save People | Sort, two-pointer (heaviest + lightest fit?) | The Gas Station insight is genuinely beautiful: the optimal start is the index immediately after the lowest cumulative balance — one O(n) pass solves it. Advanced: Greedy in Graph AlgorithmsThree of the most famous graph algorithms are *exactly* greedy: | Algorithm | Greedy choice | Justified by |
| Dijkstra's | always extract the unvisited vertex with smallest tentative distance | non-negative weights ⇒ once popped, optimal | |||
| Prim's MST | add cheapest edge crossing the cut between tree and non-tree | cut property | |||
| Kruskal's MST | add cheapest edge that doesn't create a cycle | cut property + cycle property |
Dijkstra famously breaks with negative edges — exactly because the greedy choice property fails.
a+b\ vs \b+a\ (string concat). Sort, then join.Five techniques, in order of rigor:
1. Counterexample search — try at least 5 small inputs including edge cases. If you find a failure, you don't have a greedy problem. 2. Exchange argument — show any non-greedy choice can be swapped to greedy without loss. 3. Greedy stays ahead — show that after k steps, greedy's partial answer is at least as good as any other algorithm's partial answer. 4. Induction — assume optimal up to step k, prove optimal at step k+1. 5. Matroid theory — if the problem's feasible-set structure is a *matroid*, greedy by weight is provably optimal (this is the deep reason Kruskal's works — graph forests form a matroid).
Some problems use greedy to prune the DP state space — e.g., scheduling with restrictions where greedy locks in the order, and DP optimises the assignment. LIS in O(n log n) is the cleanest example: greedy maintains a "patience-sort" tails array, but the binary-search step is essentially a DP-style optimisation.
1. Activity Selection: sort by end time, sweep. Compare against the wrong (sort by start time) variant on adversarial inputs to see it fail.
2. Fractional Knapsack: sort by value/weight ratio, fill until capacity. Verify the example \(10,60),(20,100),(30,120)\ capacity 50 gives 240.
3. Huffman Tree: build with a min-heap of frequencies; print resulting codes for "ABRACADABRA".
4. Jump Game II: minimum jumps to reach the end, O(n) with current-reach + next-reach tracking.