DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Greedy Algorithms

A greedy algorithm makes the locally best choice at every single step and never reconsiders it — a far cheaper strategy than DP's "consider every option and remember the best," often O(n log n) from one sort plus a single pass, instead of DP's cost scaling with the size of the state space. The catch is that greedy is only correct on problems where the greedy-choice property genuinely holds: the locally optimal choice at each step is guaranteed to be part of some globally optimal solution.

The exchange argument, briefly

The standard way to prove a greedy choice is safe is called an exchange argument: take any optimal solution, and show it can always be transformed into one that makes the greedy choice first, without ever making that solution worse. If that swap is always possible, choosing the greedy option first costs nothing — some optimal solution was reachable that way all along.

function maxNonOverlappingIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);   // sort by END time — the greedy choice
  let count = 0, lastEnd = -Infinity;

  for (const [start, end] of sorted) {
    if (start >= lastEnd) {           // doesn't overlap whatever was kept most recently
      count++;
      lastEnd = end;
    }
  }
  return count;
}

Sorting by end time — not start time, not duration — is exactly the greedy choice the exchange argument justifies: an interval that ends earliest leaves the most possible room for everything scheduled after it, so swapping any optimal solution's first-chosen interval for the earliest-ending compatible one never makes that solution worse. Sorting by start time or by duration instead is the classic wrong greedy heuristic for this exact problem — both look plausible, and both have easy counterexamples.

When greedy silently gives the wrong answer

// Greedy coin change — WRONG in general
function greedyCoinChange(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a);   // largest denomination first
  let count = 0;
  for (const coin of sorted) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return amount === 0 ? count : -1;
}

greedyCoinChange([1, 3, 4], 6);   // greedy returns 3 (4 + 1 + 1) — but 3 + 3 = 2 coins is optimal!

This is precisely the case where the greedy-choice property fails: taking the largest available coin at every step is not guaranteed to be part of an optimal solution for an arbitrary set of coin denominations, and {1, 3, 4} targeting 6 is a small, memorable counterexample. The fix is dynamic programming — the two previous chapters — which tries every valid coin at each amount and keeps the best result, rather than committing irrevocably to one choice and never revisiting it. This contrast is the clearest way to internalize the difference between the two families: DP is precisely what you fall back to when you can't prove — or, as here, can actively disprove — that a greedy choice is always safe.

Practice this on Code Lab: Greedy Algorithms