Greedy: commit to the best local choice, never look back

01 · Foundation

What makes greedy risky

A greedy algorithm is really a bet. At every step it assumes that whichever option looks best right now can never be beaten later by some smarter combination of choices it passed up. Sometimes that bet is correct. Sometimes it isn't — and when it isn't, greedy produces an answer that's valid but not optimal, with no way to go back and fix it.

A classic counterexample makes this concrete. Say you're making change with coin denominations [1, 3, 4] for amount 6. Greedy always grabs the largest coin that still fits:

• Take a 4 (remaining: 2)
• Take a 1 (remaining: 1)
• Take a 1 (remaining: 0)

That's 4 coins — but 3 + 3 = 6 only needs 2 coins. Greedy's very first move (grabbing the 4) locked in a decision that a smarter combination later beat. It had no way to know that in advance, and no way to undo it once made.

02 · Recognizing greedy

When greedy DOES work — the two properties

Greedy is only safe to use when a problem has both of the following, and — unlike DP — you need to actually convince yourself they hold before you trust the algorithm:

• The greedy-choice property — there is always some optimal solution that starts with the greedy (locally best) choice. Committing to it never rules out reaching the true optimum, because the optimum was reachable through that choice all along.
• Optimal substructure — the same idea DP relies on: the optimal solution to the whole problem contains optimal solutions to its subproblems. Once the greedy choice is made, what's left is a smaller version of the same problem.

The difference from DP is subtle but important. DP explores and compares multiple options at each step because it can't yet prove which one is safe — so it keeps every candidate around and lets the recurrence sort it out. Greedy has already proven, for this specific problem, that comparing is unnecessary: the locally-best choice is always safe, so there's nothing to backtrack over and nothing to keep in reserve.

Interval Scheduling is the cleanest place to see this. Given a set of overlapping intervals, sort by earliest finish time and greedily accept any interval that starts at or after the end of the last one you accepted:

03 · Method

A repeatable framework

Use this sequence whenever you suspect a problem might be a greedy candidate — including the step where you actively try to break it, since that's the step people skip.

1. 1 Define the criterion, and sort by itIdentify what makes "locally best" well-defined, then sort the input by that key — earliest end time for Interval Scheduling, lowest frequency for Huffman.
2. 2 Commit at each step, never revisitAt every step, take the locally best available option and move on. There's no reconsidering a past decision later in the same pass.
3. 3 Try to break it before you trust itActively look for a counterexample where an earlier greedy choice blocks a better overall answer. If you can construct one, greedy is wrong for this problem and you need DP instead.
4. 4 If it's safe, keep the code shortOnce the greedy-choice property is confirmed, the implementation is usually a sort plus a single linear pass — no recursion, no memo table.
5. 5 Reach for a supporting data structureGreedy often needs help making each step efficient: a min-heap for Huffman's "always merge the two least-frequent items," union-find for Kruskal's cycle check (Kruskal is covered on the Graphs theory page).

04 · Worked example

Interval Scheduling, step by step

Intervals (start, end): (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11). Sort by end time, then walk through in that order: accept an interval only if its start is at or after the end of the most recently accepted interval.

Final selection: (1,4), (5,7), (8,11) — 3 non-overlapping intervals, which is the maximum possible for this input. Notice the greedy choice never got revisited: once (1,4) was accepted, every later decision was made purely by comparing against it, never by reopening it.

Open the Interval Scheduling visualizer to watch this exact selection animate.

05 · Worked example

Huffman Coding, briefly

Huffman Coding builds an optimal prefix-free binary code for a set of characters, using their frequencies. The greedy construction:

The greedy choice here is always "merge whichever two nodes currently have the smallest frequencies" — never anything else, and never reconsidered once merged. That single rule is what gives the resulting tree its shape: characters that are frequent tend to get merged later, once larger combined nodes dominate the heap, which keeps them closer to the root and gives them shorter codes. Characters that are rare get merged early, while frequencies are still small, which pushes them deeper into the tree and gives them longer codes — exactly the trade-off an optimal prefix code should make.

See the Huffman Coding visualizer for the full merge sequence animated on real character frequencies.

06 · Complexity

How to reason about time

Greedy algorithms tend to be dominated by whatever sort or heap operations set up the ordering, with the actual greedy pass itself being cheap and linear.

• Interval Scheduling — O(n log n), dominated by sorting the intervals by end time. The greedy selection pass afterward is a single O(n) linear scan.
• Huffman Coding — O(n log n). Building the tree takes n heap extractions and roughly n insertions, and each min-heap operation costs O(log n).

Dijkstra's, Prim's, and Kruskal's algorithms are greedy too, but their complexity depends on the graph representation and heap choice — that's covered on the Graphs theory page rather than repeated here.

07 · Before you start coding

Common mistakes

• Sorting by the wrong key — e.g. by start time instead of end time for Interval Scheduling. It looks like a reasonable rule of thumb, but it produces a suboptimal answer.
• Assuming greedy always works without checking for the greedy-choice property first. Coin Change with non-canonical denominations (like [1, 3, 4]) is the classic trap.
• Confusing "a valid solution" with "the optimal solution" — greedy without the right proof can produce something that satisfies all the constraints but still isn't the best possible answer.
• For Huffman specifically, merging anything other than the two currently-smallest frequencies. Any other merge order breaks the optimality guarantee, even if it still produces a valid tree.
• Forgetting that greedy decisions are permanent — there's no "undo" step like backtracking has, so an unsafe greedy choice can't be corrected later in the same pass.

08 · Try it yourself

The two greedy visualizers on this site