Skip to content

Greedy Algorithm

In one line

A greedy algorithm makes the best local choice at each step, hoping to find a globally optimal solution.

In simple words

A greedy algorithm builds a solution step by step, always choosing the option that looks best right now (the locally optimal choice) without reconsidering past decisions. It never backtracks. When the problem has the right structure (the greedy-choice property and optimal substructure), this local strategy produces a globally optimal answer.

Classic greedy problems include the coin change problem (pick the largest denomination first), activity selection (pick the activity that ends earliest), Huffman coding (merge the two least-frequent symbols), and Dijkstra's shortest path (always expand the closest unvisited node). Kruskal's and Prim's minimum spanning tree algorithms are also greedy.

Greedy algorithms are simple and fast, but they do not work for every problem. For some problems, a greedy choice early on blocks a better overall solution. When greedy fails, dynamic programming or backtracking is needed. Proving a greedy algorithm is correct usually requires showing no better solution exists that contradicts the greedy choice.

Example

javascript
// Coin change — greedy: always use the largest coin possible
function greedyCoinChange(amount, coins) {
  coins.sort((a, b) => b - a); // descending
  const result = [];
  for (const coin of coins) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  return result;
}

console.log(greedyCoinChange(63, [25, 10, 5, 1]));
// [25, 25, 10, 1, 1, 1] — 6 coins

The greedy strategy always takes the largest coin that fits. For standard US coins this yields the optimal number of coins.

Related terms

Related Resources

Related Lessons

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors

← Back to glossary