What makes an algorithm greedy

A greedy algorithm builds a solution one step at a time, taking whatever looks best right now and never reconsidering. No backtracking, no exploring alternatives.

That makes greedy algorithms fast — usually a sort plus a linear pass — and it makes them fragile.

The coin change illustration

Make 30 from coins of 25, 10 and 5, using as few as possible.

Greedy takes 25, then cannot use 10, then takes 5: 25 + 5 = two coins. Correct.

Now make 30 from coins of 25, 10 and 1:

• Greedy: 25 + 1 + 1 + 1 + 1 + 1 = six coins.
• Optimal: 10 + 10 + 10 = three coins.

function greedyCoins(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a);
  const used = [];

  for (const coin of sorted) {
    while (amount >= coin) { used.push(coin); amount -= coin; }
  }

  return amount === 0 ? used : null;    // may fail even when a solution exists
}

Identical code, identical reasoning, and the answer is right for one coin system and wrong for another. Greedy correctness is a property of the problem, never of the algorithm.

Real currencies are designed to be canonical — greedy works on them — which is exactly why the failure is so counter-intuitive.

When greedy is provably right

Two properties must hold:

1. Greedy choice property — a globally optimal solution can be reached by making the locally optimal choice at each step.
2. Optimal substructure — an optimal solution contains optimal solutions to its subproblems.

Miss the first and you need dynamic programming, which considers alternatives instead of committing.

Greedy versus DP, in one line

Greedy commits to one choice per step: O(n log n), no memory of alternatives. DP evaluates every choice and keeps the best: slower, always correct where it applies.

If you cannot argue why the greedy choice is safe, assume it is not — and reach for DP. The next lesson is about making that argument properly.