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

Part 13 of 16 · ~4 min

Greedy Algorithms

Commit to whatever looks best right now and never revisit that decision — far cheaper than DP's habit of weighing every option and remembering the winner. A sort followed by a single pass is a typical greedy budget, O(n log n) total, next to a cost that grows with the size of DP's entire state table. The catch: this only pays off when a problem actually has the greedy-choice property, meaning the move that looks best in the moment is provably part of some fully optimal solution. Skip verifying that, and greedy hands back a fast, confident, wrong answer just as easily as a correct one.

Proving a greedy move is actually safe

There's a named technique for justifying a greedy choice rather than just hoping it works: grab any solution that's already known to be optimal, and show you can always edit it — swap one piece for the greedy pick — without making it any worse. Pull that off and the greedy choice was free all along, since some optimal answer was reachable through it from the start. This move goes by "exchange argument," and it's worth having a mental slot for the name even if the mechanics matter more.

A student is comparing every section of a popular elective across different time slots and wants the maximum number of non-overlapping ones they could theoretically attend:

function maxNonOverlappingSections(sections) {                // sections: [start, end] pairs
  const sorted = [...sections].sort((a, b) => a[1] - b[1]);   // sorted by END time — the greedy pick
  let count = 0, lastEnd = -Infinity;

  for (const [start, end] of sorted) {
    if (start >= lastEnd) {           // no overlap with whatever's currently held
      count++;
      lastEnd = end;
    }
  }
  return count;
}

maxNonOverlappingSections([[1, 3], [2, 4], [3, 5], [6, 8]]);   // 3 — [1,3], [3,5], [6,8]

Sorted by end time, [1,3] is kept first (lastEnd = 3). [2,4] starts at 2 — before lastEnd — so it's skipped. [3,5] starts right at 3, which clears the bar, and is kept (lastEnd = 5). [6,8] clears it too. Three sections survive, not two — sorting by start time instead would have locked in [1,3] and then missed [3,5] entirely by grabbing [2,4] too early.

Why the end time specifically, and not when a section starts or how long it runs: whatever finishes soonest frees up the most room for everything that comes after it, so any optimal picks can always be rearranged to put the earliest-finishing compatible option first, at no cost. The two things people reach for instead — ranking by start time, or by shortest duration — both sound defensible and both collapse the moment you try a handful of sections by hand.

Where greedy quietly gets it wrong

A student needs exactly 8 more credits, and a naive planner feature fills the gap by grabbing the largest available course size first:

// Greedy credit-gap filler — WRONG in general
function greedyFillCreditGap(availableSizes, remaining) {
  const sorted = [...availableSizes].sort((a, b) => b - a);   // largest size first
  let count = 0;
  for (const size of sorted) {
    while (remaining >= size) {
      remaining -= size;
      count++;
    }
  }
  return remaining === 0 ? count : -1;
}

greedyFillCreditGap([1, 4, 5], 8);   // greedy: 5+1+1+1 = 4 courses — but 4+4 = 2 is better

This is the greedy-choice property breaking down in the open: nothing about always grabbing the biggest size guarantees it fits into some optimal answer, once the set of available sizes is arbitrary. {1, 4, 5} against a target of 8 is small enough to keep in your head as the standing counterexample — greedy commits to the 5-credit course immediately, then has nothing left but 3 one-credit courses to mop up the remainder. Dynamic programming, from the previous two chapters, doesn't commit early: it checks every valid size against every remaining total and only settles on the best result once it's actually seen all of them. That's the real dividing line between the two families — greedy is a bet you can only place once you've proven it always pays off, and DP is what you fall back on the moment that bet can't be proven, or, like here, has already been shown to lose.

Greedy Algorithms on Code Lab.