loading
loading
loading
loading
Make the locally-best choice at every step, never reconsider it, and — for the specific class of problems where this provably reaches the global optimum — end up with the right answer in a single pass.
A greedy algorithm builds a solution one locally-optimal choice at a time and never revisits that choice. This is fast — usually a single sorted pass — but only correct for problems with the greedy choice property (a locally optimal choice is always part of some globally optimal solution) and optimal substructure. Activity Selection, interval scheduling, and Huffman coding all have this property and admit clean greedy proofs; problems like 0/1 Knapsack look similar on the surface but provably don't, which is exactly why they need dynamic programming instead.
Step through greedy algorithms live, one move at a time — this becomes a fully interactive visualizer.
Coming soonfunction activitySelection(activities) {
// Each activity: { start, end }. Sort by end time — the greedy choice.
const sorted = [...activities].sort((a, b) => a.end - b.end);
const selected = [sorted[0]];
let lastEnd = sorted[0].end;
for (let i = 1; i < sorted.length; i++) {
if (sorted[i].start >= lastEnd) { // no overlap with the last selected activity
selected.push(sorted[i]);
lastEnd = sorted[i].end;
}
}
return selected;
}// Correct for US coins (1, 5, 10, 25) but NOT for arbitrary coin sets —
// contrast with the Dynamic Programming topic's Coin Change, which is
// always correct because it checks every combination instead of assuming
// the largest coin first is always safe.
function greedyChange(coins, amount) {
const sorted = [...coins].sort((a, b) => b - a); // largest first
const used = [];
for (const coin of sorted) {
while (amount >= coin) {
amount -= coin;
used.push(coin);
}
}
return amount === 0 ? used : null; // null: greedy failed to make exact change
}// Repeatedly merge the two least-frequent nodes — the greedy choice —
// until one tree remains. A min-heap (see Heaps & Priority Queues) makes
// each "find the two smallest" step O(log n) instead of a linear scan.
function huffmanTree(frequencies) {
const heap = Object.entries(frequencies)
.map(([char, freq]) => ({ char, freq, left: null, right: null }));
while (heap.length > 1) {
heap.sort((a, b) => a.freq - b.freq); // stand-in for a real min-heap
const a = heap.shift();
const b = heap.shift();
heap.push({ char: null, freq: a.freq + b.freq, left: a, right: b });
}
return heap[0]; // root — frequent characters end up near the root (short codes)
}| Greedy | Dynamic Programming | |
|---|---|---|
| Choice revisited? | Never — locally-best, made once | Effectively yes — every subproblem's options considered |
| Requires proof of | The greedy choice property (exchange argument) | Optimal substructure + overlapping subproblems |
| Typical time | O(n log n) — usually just a sort | O(n · target) or worse — proportional to subproblem count |
| When it's wrong | Silently gives a suboptimal answer, no error | N/A — DP is always correct once applicable |
| Classic example | Activity Selection, Huffman coding | 0/1 Knapsack, Coin Change (general coin sets) |
Greedy-by-value-density (always take the item with the best value-to-weight ratio that still fits) looks reasonable but is provably wrong for 0/1 Knapsack: a high-ratio item can be small enough that taking it wastes capacity that two lower-ratio items would have filled more valuably together. Because items can't be split, an early greedy pick can lock out a better combination — there's no exchange argument that saves it. This is precisely why Knapsack needs the Dynamic Programming topic's two-dimensional table instead: it has to consider combinations, not just a single locally-best order.
Greedy largest-coin-first works for 'canonical' coin systems like US currency (1, 5, 10, 25) but fails for an arbitrary coin set — e.g., coins {1, 3, 4} making 6: greedy takes 4 then two 1s (three coins), but 3+3 (two coins) is strictly better. The greedy choice property doesn't hold here, which is exactly why the Dynamic Programming topic's Coin Change example checks every coin at every amount instead of assuming the largest is always safe.
Given a connected weighted graph, a Minimum Spanning Tree (MST) connects every node with the least total edge weight, using no cycles. Two greedy strategies both provably reach the MST, from different starting rules: Kruskal's algorithm sorts all edges by weight and greedily adds each one that doesn't create a cycle (checked with a union-find structure); Prim's algorithm grows a single tree from one start node, greedily adding the cheapest edge that connects the growing tree to a new node (a min-heap, exactly like Dijkstra's priority queue, makes 'cheapest edge out' efficient). Both are greedy, both are provably optimal for this specific problem, and both need infrastructure this platform already teaches — sorting and union-find for Kruskal, a priority queue for Prim.
Huffman coding assigns shorter binary codes to more frequent characters, minimizing total encoded length, by repeatedly merging the two least-frequent remaining nodes into a new parent node until one tree remains. The greedy choice — always merge the two smallest — is what guarantees frequent characters end up near the root (short codes) and rare ones end up deep (long codes). A min-heap (see Heaps & Priority Queues) is exactly the right structure for repeatedly finding 'the two smallest' efficiently.
Most greedy interview problems reduce to one of a few shapes: interval/activity selection (sort by end time), fractional resource allocation (sort by ratio — and check whether the problem allows fractional pieces, since that's what separates Fractional Knapsack, where greedy works, from 0/1 Knapsack, where it doesn't), and merge/build-tree problems (Huffman's repeated-smallest-pair pattern). When asked to justify a greedy solution, state the greedy choice rule explicitly and sketch the exchange argument — 'it seems to work on examples' is not a proof.
Try to prove the greedy choice property with an exchange argument: take any optimal solution, show it can be modified to start with the greedy choice without getting worse. If you can't construct that argument — or worse, can find a counterexample where the greedy choice provably blocks the optimum (like 0/1 Knapsack or general Coin Change) — it isn't greedy, and needs dynamic programming instead.
Yes, when a problem genuinely has the greedy choice property, greedy is faster — usually O(n log n) from a single sort, versus DP's cost proportional to the number of subproblems. The catch is that far fewer problems actually qualify for greedy than initially appear to.
Nothing structurally — they're the same problem (maximize non-overlapping intervals) under different names from different textbooks. The earliest-finish-time greedy rule and its exchange-argument proof apply identically to both.
At each step, Prim's must find the cheapest edge connecting the growing tree to any new node — exactly the 'extract the smallest' operation a min-heap does in O(log n), the same priority-queue role it plays in Dijkstra's algorithm.
Share what clicked for you and see notes from other learners on this topic.
Coming soon