What are greedy algorithms, and when do they work?

Question

Accepted Answer

A **greedy algorithm** makes the **locally optimal choice** at each step, hoping it leads to a global optimum. It is simple and fast, but only correct when the problem has the **greedy-choice property** and **optimal substructure**.

## The idea

Never reconsider past choices — commit to the best immediate option and move on.

## Example: coin change with canonical coins

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

This is optimal for US coins, but **fails** for sets like {1, 3, 4} where greedy gives 4+1+1 for 6 instead of 3+3.

## When greedy works

- **Optimal substructure:** an optimal solution contains optimal sub-solutions.
- **Greedy-choice property:** a local optimum is part of a global optimum.

Examples that work: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.

## Complexity

Usually fast — often O(n log n) after sorting.

## Pitfalls

Greedy is **not always correct**. Prove the greedy-choice property or test against a brute-force/DP baseline before trusting it.

## Why it matters

When greedy applies, it is far simpler and faster than DP or brute force.

Knowing *when* it is valid — and when it silently gives wrong answers — is a mark of algorithmic maturity.

Many cornerstone graph algorithms are greedy at heart.