Greedy Algorithms

Imagine you're at a till and you owe someone 87 pence in change. You reach into a drawer of UK coins and, without any planning, you do the obvious thing: grab the biggest coin that still fits — a 50p — then the biggest that fits into what's left, and again, and again, until the change is exact. No lists of options, no looking ahead, no working out every combination. Just "take the best coin available right now" over and over.

That instinct has a name. A greedy algorithm builds a solution one step at a time, and at every step it makes the choice that looks locally best at that moment — grabbing the immediate reward — and never goes back to reconsider. It hopes that a chain of locally best choices adds up to a good overall answer.

It is wonderfully simple to write — usually just "sort, then loop and take the best each time".
It is typically very fast — it commits to a choice and moves on, never exploring the huge tree of alternatives.
For some problems it provably gives the optimal answer. For others it can be fooled into a poor one — the catch we'll meet later.

The classic example: making change

The textbook greedy problem is the coin-change problem: pay an exact amount using as few coins as possible. The greedy rule is a single sentence:

Repeatedly take the largest coin that does not exceed the amount still owed, subtract it, and continue until the amount owed is zero.

Let's chase 87p through it with UK coins (values in pence: 1, 2, 5, 10, 20, 50, 100, 200). At each step we look at what's left, pick the biggest coin that fits, and watch the remainder shrink. Step through it:

Five coins — 50 + 20 + 10 + 5 + 2 = 87 — and for British coins that really is the fewest possible. Notice how the algorithm never reconsiders an earlier coin: once the 50p is taken, it's committed forever.

Making change, in code

The rule translates almost word-for-word into TypeScript. We list the coin values from largest to smallest, then for each value we grab as many of that coin as will fit before moving down to the next. Press Run and read the coins it chose:

The whole thing is one pass down a short list of coin values. There's no searching, no trying of combinations, no undo. That directness is exactly why greedy algorithms are so appealing.

Why is it so fast?

Compare greedy with the "obviously safe" alternative: try every combination of coins and keep the smallest. The number of combinations explodes as the amount grows, so that brute-force search is hopeless for large amounts. The greedy version, by contrast, does a fixed amount of work per coin value — it's essentially O(1) in the number of coin types and never revisits a decision.

This is the heart of the greedy trade-off: you swap the guarantee of an exhaustive search for enormous speed. When greedy is correct for your problem, that's a spectacular bargain. When it isn't, that speed is buying you a wrong answer — which brings us to the essential warning.

It is tempting to believe that always grabbing the biggest coin must give the fewest coins. It doesn't — it only happens to for coin systems (like the UK's) that are specially shaped. Change the coins and greedy can lose.

Suppose a country used only 4p, 3p and 1p coins, and you must make 6p. Greedy grabs the biggest coin that fits — a 4p — leaving 2p, which it pays with 1 + 1. That's 4 + 1 + 1: three coins. But a moment's thought finds 3 + 3: two coins. Greedy walked straight past the better answer because taking the 4p looked best at the time. Run it and see:

The lesson is not "avoid greedy" — it's that a greedy algorithm gives an answer, but not necessarily the best answer. You must prove (or at least carefully verify) that the greedy choice is safe for your particular problem before you trust it. For "well-behaved" coin systems it is provably optimal; for arbitrary ones you need a different technique (dynamic programming) to guarantee the minimum.

Greedy beyond coins

The pattern — sort by "best", then repeatedly take the best that's still allowed — shows up all over computer science. A few you'll meet again:

Activity selection: fit the most non-overlapping events into a day by always choosing the event that finishes earliest next. (Here greedy is provably optimal.)
Huffman coding: build an optimal compression code by repeatedly merging the two least-frequent symbols. (Optimal.)
Dijkstra's shortest-path and Prim's/Kruskal's minimum-spanning-tree algorithms all make a locally best edge choice at each step. (Optimal for those problems.)
The travelling salesman "nearest neighbour" heuristic: always drive to the closest unvisited city. Fast and simple — but often not the shortest tour.

Notice the split: for some of these, greedy is a theorem-backed optimal method; for others it's a quick heuristic that gives a decent-but-not-guaranteed answer. Both are legitimate uses — you just have to know which one you're in.

A greedy algorithm makes two commitments that define it. First, it decides using only what it can see now — never by looking ahead at how a choice plays out later. Second, it is irrevocable: once a choice is made it is never undone. That's the opposite of approaches like backtracking or dynamic programming, which explore alternatives and can change their minds. The pay-off for greedy's tunnel vision is speed and simplicity; the price is that it can march confidently to a suboptimal answer.