Greedy Algorithms: Introduction

A greedy algorithm builds up a solution one step at a time, always taking the choice that looks best right now — the locally optimal move — and never reconsidering it. When the problem has the right structure, this short-sighted strategy still lands on the globally optimal answer, and it does so fast and with very little code.

This page explains what “greedy” really means and the two properties a problem must have for greedy to be correct: the greedy-choice property and optimal substructure.

The core idea: never look back

Most algorithm strategies explore alternatives. Dynamic programming tries many combinations; backtracking undoes wrong turns. A greedy algorithm does neither — it commits to the best immediate option and moves on. Picture making change: to hand back the fewest coins, you keep grabbing the largest coin that still fits. No undo, no second-guessing.

Here is that “grab the biggest coin that fits” loop in all four languages — switch the tab to your language:

#include <vector>
int coinCount(int amount, std::vector<int> coins) { // coins sorted descending
    int count = 0;
    for (int c : coins) {
        count += amount / c; // take as many of this coin as fit
        amount %= c;         // keep the remainder
    }
    return count;            // correct only for "canonical" coin systems
}

int coinCount(int amount, int[] coins) { // coins sorted descending
    int count = 0;
    for (int c : coins) {
        count += amount / c; // take as many of this coin as fit
        amount %= c;         // keep the remainder
    }
    return count;            // correct only for "canonical" coin systems
}

function coinCount(amount, coins) { // coins sorted descending
  let count = 0;
  for (const c of coins) {
    count += Math.floor(amount / c); // take as many as fit
    amount %= c;                     // keep the remainder
  }
  return count; // correct only for "canonical" coin systems
}

def coin_count(amount, coins):  # coins sorted descending
    count = 0
    for c in coins:
        count += amount // c    # take as many of this coin as fit
        amount %= c             # keep the remainder
    return count                # correct only for "canonical" coin systems

For beginners: “Locally optimal” just means best at this single step. “Globally optimal” means best for the whole problem. Greedy bets that a chain of locally best moves adds up to the global best — a bet that only pays off for certain problems.

Property 1: the greedy-choice property

A problem has the greedy-choice property if a globally optimal solution can be reached by making the locally optimal (greedy) choice at each step. In other words, the greedy choice made first is safe — there is always some optimal solution that contains it. You never have to consider the consequences of not making it.

This is the property that makes greedy different from dynamic programming. DP makes a choice only after solving subproblems and comparing them; greedy makes the choice first, then solves the single subproblem that remains.

Property 2: optimal substructure

A problem has optimal substructure if an optimal solution to the whole problem contains optimal solutions to its subproblems. After you make the greedy choice, you are left with a smaller version of the same problem — and solving that optimally, combined with your choice, gives the overall optimum.

Optimal substructure is shared with dynamic programming. The extra ingredient greedy needs is the greedy-choice property: that the first choice can be fixed without looking ahead.

Going deeper: Both properties must hold. Optimal substructure alone gives you DP; add a provable greedy-choice property and you can skip the bookkeeping and just commit. If only the greedy-choice intuition holds but substructure breaks, the algorithm is plain wrong on some inputs.

A template for greedy algorithms

Nearly every greedy algorithm follows the same shape:

1. Define a selection rule  (what does "best right now" mean?)
2. Often: sort or use a heap to fetch the best candidate fast
3. Repeat: take the best valid candidate, commit, shrink the problem
4. Return the assembled solution

The hard part is never the loop — it is choosing the right selection rule and proving it is safe. Sorting by the wrong key gives a fast algorithm that is confidently wrong.

Why greedy is worth learning

• Speed. Greedy solutions are usually O(n log n) (dominated by a sort) or O(n), and use O(1) extra space — far cheaper than DP’s tables.
• Simplicity. Once the selection rule is right, the code is tiny.
• Real systems. Scheduling, data compression (Huffman coding), and shortest-path algorithms like Dijkstra’s and minimum spanning trees are all greedy at heart.

Pitfall: Greedy feels obviously correct and is wrong surprisingly often. The standard coin system makes greedy work, but with coins {1, 3, 4} and amount 6, greedy gives 4+1+1 (three coins) while the optimum is 3+3 (two). Never ship a greedy algorithm without checking it actually applies.

Next: learn exactly when greedy works — and how to prove or disprove it — then see it in action with activity selection.

Key terms

• Greedy choice — the locally optimal option taken at each step, never revisited.
• Greedy-choice property — making the greedy choice first still allows a globally optimal solution.
• Optimal substructure — an optimal solution is built from optimal solutions to subproblems.