What you'll learn

  1. Quick answer
  2. The approach
  3. Where it works: coin change with Indian denominations
  4. Where it fails, on the same code
  5. How to tell whether greedy is safe
  6. The classic greedy problems
  7. FAQ

Quick Answer

Greedy means making the locally best choice at each step. It works when the problem has the greedy-choice property — that a local optimum leads to a global one. When it does not, greedy gives a wrong answer with no indication anything went wrong.

The approach

At each step, take whatever looks best right now, commit to it, and never revisit. No backtracking, no exploring alternatives.

That makes greedy algorithms fast and simple — usually a sort followed by a single pass. It also makes them fragile, because a choice that looks best locally can foreclose a better overall answer.

The interesting question is never "how do I write a greedy algorithm" — that part is easy. It is "is greedy correct for this problem?"

Where it works: coin change with Indian denominations

def greedy_coins(amount, coins):
    coins = sorted(coins, reverse=True)
    out = []
    for c in coins:
        while amount >= c:
            out.append(c)
            amount -= c
    return out, amount

print(greedy_coins(87, [1, 2, 5, 10, 20, 50]))
# ([50, 20, 10, 5, 2], 0)

Five coins for 87, and that is optimal. Take the largest coin that fits, repeat. It works here because of a specific property of this denomination set: every coin is at least double the next one down, so no combination of smaller coins can substitute more efficiently for a larger one.

Most real currency systems are designed this way deliberately, which is why the greedy approach feels natural — it is how people actually give change.

Where it fails, on the same code

Change the denominations and the identical algorithm produces a worse answer:

print(greedy_coins(6, [1, 3, 4]))
# ([4, 1, 1], 0)   -- 3 coins

Greedy takes 4, then must take 1 and 1. Three coins. But 3 + 3 is two coins, and greedy never considers it because taking 4 looked better at the time.

Notice what did not happen: no error, no warning. The function returned a valid set of coins summing to 6. It was simply not the best one, and nothing in the output indicates that.

This is the danger of greedy algorithms. A wrong greedy solution looks exactly like a right one, which is why proving correctness matters more here than in most areas.

The correct approach for arbitrary denominations is dynamic programming, which considers every combination — slower, and correct for any coin set.

How to tell whether greedy is safe

Two properties must hold, and both have names interviewers use:

  • Greedy choice property — a globally optimal solution can be reached by making locally optimal choices. This is the one that fails in the coin example.
  • Optimal substructure — an optimal solution contains optimal solutions to its subproblems. Dynamic programming needs this too.

In practice, the fastest check is to hunt for a counterexample. Try to construct a small input where taking the best-looking option leads somewhere worse. If you find one, greedy is out. If you genuinely cannot after real effort, greedy is probably right — and in an interview, saying "I tried to break it with X and Y and could not" is a strong justification.

Never assume greedy works because it passes the sample cases. The failing coin example passes any test that only checks the total.

The classic greedy problems

These recur constantly and are worth recognising:

  • Activity selection — the most meetings fitting in one room. Sort by end time and take each that fits. Sorting by start time or by duration both fail, which makes it a good illustration that the greedy criterion matters as much as the strategy.
  • Fractional knapsack — take items by value-to-weight ratio. Greedy is optimal because you can take fractions. The 0/1 knapsack, where items are indivisible, needs dynamic programming.
  • Huffman coding — repeatedly merge the two least frequent symbols. Provably optimal, and the basis of real compression.
  • Minimum spanning tree — Kruskal's and Prim's algorithms are both greedy and both provably correct. Kruskal's uses union-find to detect cycles.

The activity selection and knapsack pairs are the most useful to internalise, because each shows a nearly identical problem where greedy is optimal in one form and wrong in another.

Frequently Asked Questions

What is the difference between greedy and dynamic programming? Greedy makes one choice at each step and never reconsiders. Dynamic programming explores all choices and reuses subproblem results. Greedy is faster; DP is correct in cases where greedy is not.
How do I know if a greedy approach is correct? Try hard to build a counterexample where a local optimum leads to a worse global result. Failing that, argue the greedy choice property explicitly. Passing sample tests proves nothing, since a wrong greedy answer is still a valid-looking one.
Why does greedy work for Indian coins but not for [1, 3, 4]? Because in the Indian set each denomination is at least double the next, so smaller coins can never substitute more efficiently. With [1,3,4], taking 4 for a total of 6 forces two 1s, where two 3s would have been better.
Is Dijkstra's algorithm greedy? Yes. It repeatedly takes the closest unvisited node and finalises it. That greedy choice is provably safe only because edge weights are non-negative.
Why sort by end time in activity selection? Finishing earliest leaves the most remaining time for other activities. Sorting by start time or shortest duration both produce counterexamples, which shows the criterion matters as much as the strategy.