Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, never looking back or reconsidering previous decisions. When it works, it’s elegant and efficient — often O(n log n) with a sort step. The challenge is knowing when it works, because a greedy approach that looks right can produce subtly wrong answers.

The Greedy Choice Property

A problem has the greedy choice property if a globally optimal solution can always be built by making the locally optimal (greedy) choice at each step. This is the key property you need to verify before committing to a greedy approach.

Combined with optimal substructure (same requirement as DP), a greedy algorithm is correct and usually faster than DP.

NOTE

The difference between greedy and DP: greedy makes one irrevocable choice at each step. DP considers all choices and picks the best. Greedy is faster but only works on a subset of problems where the local choice is provably safe.

Coin Change — When Greedy Works (and When It Doesn’t)

Problem: Given coin denominations and a target amount, find the minimum number of coins.

When greedy works: standard denominations (1, 5, 10, 25)

function coinChangeGreedy(coins: number[], amount: number): number {
  // Requires coins to be sorted descending
  const sorted = [...coins].sort((a, b) => b - a);
  let count = 0;
  let remaining = amount;

  for (const coin of sorted) {
    count += Math.floor(remaining / coin);
    remaining %= coin;
  }

  return remaining === 0 ? count : -1;
}

coinChangeGreedy([25, 10, 5, 1], 41);
// 25 + 10 + 5 + 1 = 41 → 4 coins ✓

When greedy fails: non-standard denominations

// Coins: [1, 3, 4], target: 6
// Greedy: 4 + 1 + 1 = 3 coins
// Optimal: 3 + 3   = 2 coins ✗

WARNING

Greedy coin change only works for coin systems where every larger denomination is a multiple of smaller ones (like US coins). For arbitrary denominations, you must use dynamic programming. This is one of the most common “trap” problems in interviews — make sure you know which approach to use.

Activity Selection — A Classic Greedy Win

Problem: Given n activities with start and end times, select the maximum number of non-overlapping activities.

Greedy strategy: Always pick the activity that finishes earliest (among those compatible with already-chosen activities).

interface Activity {
  start: number;
  end: number;
  name: string;
}

function activitySelection(activities: Activity[]): Activity[] {
  // Sort by end time
  const sorted = [...activities].sort((a, b) => a.end - b.end);
  const selected: Activity[] = [];
  let lastEnd = -Infinity;

  for (const activity of sorted) {
    if (activity.start >= lastEnd) {
      selected.push(activity);
      lastEnd = activity.end;
    }
  }

  return selected;
}

const activities: Activity[] = [
  { start: 1,  end: 4,  name: "A" },
  { start: 3,  end: 5,  name: "B" },
  { start: 0,  end: 6,  name: "C" },
  { start: 5,  end: 7,  name: "D" },
  { start: 8,  end: 9,  name: "E" },
  { start: 5,  end: 9,  name: "F" },
];

activitySelection(activities);
// → [A, D, E]: finish at 4, 7, 9 — 3 activities (optimal)

Why does “earliest end time” work? Finishing earlier leaves the most remaining time for future activities. Any other selection of the first activity either uses the same or more future time, so it can never be better.

TIP

To prove a greedy strategy is correct, use an exchange argument: assume an optimal solution doesn’t make the greedy choice. Show that you can swap in the greedy choice without making the solution worse. This is the standard technique for greedy correctness proofs.

More Greedy Algorithms You’ll Encounter

Problem	Greedy Strategy
Huffman encoding	Always merge the two lowest-frequency nodes
Minimum spanning tree (Kruskal’s)	Always pick the cheapest edge that doesn’t create a cycle
Dijkstra’s shortest path	Always process the unvisited node with smallest known distance
Fractional knapsack	Always take the highest value-per-weight item first
Task scheduling (minimize lateness)	Sort tasks by deadline

IMPORTANT

The 0/1 knapsack (where you can’t take fractions) is not solvable with greedy — it requires dynamic programming. The fractional knapsack (where you can take partial items) is solvable with greedy. This distinction is a classic interview question.

Greedy vs DP Decision Guide

Ask these questions in order:

Can I prove the greedy choice property? (exchange argument)
Does the problem have optimal substructure?
If both: use greedy — simpler and faster
If only optimal substructure: use DP
If neither: try brute force, backtracking, or problem reformulation

Further Learning

Search these terms to go deeper:

“Greedy algorithm correctness proof exchange argument” — how to rigorously verify a greedy strategy
“Huffman coding greedy algorithm compression” — real application of greedy in data compression
“Kruskal Prim minimum spanning tree” — two greedy approaches to a famous graph problem
“Interval scheduling greedy problems leetcode” — practice set for activity-selection-style problems
“Fractional vs 0/1 knapsack comparison” — the canonical example of when greedy works vs when it doesn’t

Greedy Algorithms

A greedy algorithm always grabs the best-looking option right now, without worrying about the future. It’s how you make change: reach for the biggest coin that fits, repeat. When this “best-for-now” strategy happens to give the best overall answer, greedy is wonderfully simple and fast. The catch is knowing when it actually works.

Making change: greedy in action

To make 41¢ with coins [25, 10, 5, 1], grab the biggest that fits each time:

function coinChange(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a)  // biggest first
  let count = 0, left = amount
  for (const coin of sorted) {
    count += Math.floor(left / coin)   // take as many as fit
    left %= coin
  }
  return left === 0 ? count : -1
}
// 25 + 10 + 5 + 1 = 41 → 4 coins ✅

Where greedy goes wrong

Greedy doesn’t always win. With weird coins [1, 3, 4] making 6:

Greedy grabs 4, then 1, then 1 → 3 coins.
But 3 + 3 → 2 coins is better!

Greedy took the shiny 4 and missed the smarter combo.

WARNING

Greedy coin change only works for “nice” coin systems (like real money, where each coin is a clean multiple of smaller ones). For arbitrary coins, you need dynamic programming instead. This is a classic interview trap.

When greedy shines: picking activities

Given events with start/end times, how many non-overlapping ones can you attend? Greedy nails this: always pick the event that ends earliest, then the next one that starts after it, and so on.

function selectActivities(activities) {
  const sorted = [...activities].sort((a, b) => a.end - b.end)  // earliest finish first
  const chosen = []
  let lastEnd = -Infinity
  for (const a of sorted) {
    if (a.start >= lastEnd) {   // doesn't overlap
      chosen.push(a)
      lastEnd = a.end
    }
  }
  return chosen
}

Why does “finish earliest” work? Ending sooner leaves the most time for more events — a locally smart choice that also happens to be globally best.

Greedy vs dynamic programming

Greedy commits to one choice at each step and never reconsiders. Fast, but only correct for certain problems.
DP considers all the options and picks the best. Slower, but works on more problems.

The skill is recognizing which one a problem needs. When in doubt (like weird coin sets), reach for DP.

In one sentence

A greedy algorithm always takes the best immediate option — fast and elegant when the local choice is provably safe (like picking earliest-finishing events), but wrong for cases like odd coin systems, where dynamic programming is needed.

Want to go deeper?

Switch to Expert mode above for the greedy-choice property, exchange-argument proofs, and famous greedy algorithms (Huffman, Dijkstra, Kruskal).