A greedy algorithm builds a solution one step at a time, always taking whatever choice looks best right now, and never reconsidering that choice later. No backtracking, no exploring alternatives, no cache of subproblem answers — just a sequence of locally optimal decisions. That simplicity makes greedy algorithms fast and easy to reason about, but it only produces a correct answer for a specific class of problems. Knowing which class is the entire skill.
What changed in 2026
- The core technique is unchanged, but recognizing that a problem is greedy-shaped rather than DP-shaped continues to be one of the more commonly misjudged calls in technical interviews and real optimization code alike.
- Greedy heuristics remain the practical backbone of large-scale scheduling and resource allocation systems, where a provably optimal solution is too slow to compute and a good-enough greedy approximation ships instead.
- Greedy-based approximation algorithms saw continued use in large routing and clustering problems, where exact optimization does not scale and a bounded-error greedy approach is the pragmatic tradeoff.
The greedy choice property
A greedy algorithm only produces a correct, optimal answer when the problem has the greedy choice property: a locally optimal choice at each step leads to a globally optimal solution, with no need to revisit earlier choices. Proving this formally usually uses an exchange argument, showing that any optimal solution can be rearranged to match the greedy choice without getting worse. Most textbooks skip the proof and just show the pattern; trust it for the classic problems below, and stay skeptical of a new problem until a proof or counterexample can be found.
Classic examples that work
Coin change (canonical denominations, e.g. US coins):
amount = 67
greedy: take the largest coin <= remaining amount, repeat
25 + 25 + 10 + 5 + 1 + 1 = 67 (6 coins, optimal for this coin system)
- Activity selection: given a set of activities with start and end times, pick the maximum number that do not overlap. Sorting by end time and greedily picking the next compatible activity is provably optimal.
- Huffman coding: build an optimal prefix-free compression code by always merging the two least-frequent nodes first.
- Dijkstra's algorithm: always finalize the closest unvisited vertex next — a greedy choice that happens to be provably correct for non-negative-weight graphs.
- Minimum spanning tree, Kruskal or Prim: always add the cheapest edge that does not create a cycle.
Where greedy fails
Coin change (non-canonical denominations):
coins = [1, 3, 4], amount = 6
greedy: take 4, then 1, then 1 = 3 coins (4+1+1)
optimal: take 3, then 3 = 2 coins (3+3)
The greedy choice — always take the largest coin — is wrong here because taking a 4 first blocks the better 3-plus-3 combination. This is the standard demonstration that greedy is not a general-purpose technique: it needs the greedy choice property to hold, and most problems do not guarantee it without proof.
Greedy vs dynamic programming
| Property |
Greedy |
Dynamic programming |
| Decisions |
One pass, never revisited |
Considers multiple options, keeps the best |
| Speed |
Usually O(n log n) or better |
Usually O(n times states), slower |
| Correctness |
Only when greedy choice property holds |
Correct whenever optimal substructure holds |
| Memory |
O(1) extra, typically |
O(n) or more, for the cache or table |
| Example |
Activity selection |
0/1 knapsack |
The 0/1 knapsack problem is the sharpest illustration: greedy, always take the best value-to-weight ratio item, fails because taking an item is irreversible even when a different combination would have been better, while DP correctly considers both including and excluding each item.
Common pitfalls
Assuming greedy works without checking the greedy choice property. This is the single biggest source of subtly wrong optimized code — it often produces a good-looking answer that is not actually optimal, and the bug only shows up on specific inputs.
Using greedy for 0/1 knapsack-style problems. Any problem where taking an item now can block a better combination later signals that greedy will fail and DP is needed instead.
Not sorting first when the problem needs it. Many greedy algorithms, including activity selection, Huffman coding, and interval scheduling, depend entirely on processing items in the right sorted order — skipping the sort silently breaks correctness.
FAQ
How can a problem be checked for whether it is solvable greedily?
Look for the greedy choice property and optimal substructure together. Without a clean proof or counterexample, test a brute-force solution against the greedy one on small random inputs before trusting it.
Is Dijkstra's algorithm a greedy algorithm?
Yes — it is one of the most cited examples of a provably correct greedy algorithm, specifically because non-negative edge weights guarantee the locally closest vertex is genuinely part of the globally shortest path.
Can a greedy algorithm be combined with dynamic programming?
Not usually within the same subproblem — they represent different decision strategies. But a larger system can use greedy for one stage, such as an initial heuristic solution, and DP or exact optimization for a refinement stage.
Where to go next