Greedy Algorithms

How It Works

A greedy algorithm builds a solution incrementally by always making the choice that looks best right now, without reconsidering it later. There's no backtracking and no exploring alternatives; each decision is final. This makes greedy algorithms fast (usually a single linear pass, sometimes preceded by a sort) but it only produces the correct answer when the problem has the greedy-choice property: the locally optimal choice at each step is provably part of some globally optimal solution.

The typical workflow is: (1) figure out what to sort by, if anything, so the "obviously best" choice is always at the front; (2) walk through the input once, at each step either taking the current item or updating a running best; (3) never revisit a prior decision. For example, in "Best Time to Buy and Sell Stock," you track the lowest price seen so far and the best profit so far; you never need to go back and reconsider an earlier buy day once you've moved past it.

The hard part of greedy problems isn't usually the implementation; it's convincing yourself (or your interviewer) that the greedy choice is actually safe. If you can't construct a proof or a strong intuition for why the local choice never hurts the global answer, the problem probably needs DP instead.

When To Use It

• A single optimal number is required, computed in one linear pass: max profit, minimum jumps, minimum coins in specific coin systems, minimum platforms/rooms needed.
• Sorting reveals the obviously correct order: interval scheduling problems become greedy once sorted by end time (or start time, depending on the question); assignment problems become greedy once both sides are sorted.
• Exchange argument holds: if you can show that swapping any two adjacent choices in an alternative solution never makes it better, greedy is safe.
• Interval overlap / scheduling: "minimum intervals to remove so none overlap," "maximum number of non-overlapping intervals," and "minimum resources to handle all intervals" are classic greedy-after-sort problems.
• DP would work but is unnecessary: if each decision doesn't actually depend on unresolved future state, a DP table is solving a problem that a single pass already solves optimally.

Time & Space Complexity

Most greedy algorithms run in O(n) if no sorting is needed (buy/sell stock, jump game, gas station) or O(n log n) if a sort is required first (non-overlapping intervals, task scheduler with a heap). Space is typically O(1) beyond the input, since greedy only needs to track a small amount of running state (current best, current window bound, current count) rather than a full DP table.

// Greedy template: sort if needed, then make one irrevocable choice per step
function greedySelect(items) {
  items.sort((a, b) => a.key - b.key); // choose the sort key that exposes the safe local choice

  let result = initialValue();
  let runningState = initialState();

  for (const item of items) {
    if (isCompatible(item, runningState)) {
      result = updateResult(result, item);
      runningState = updateState(runningState, item);
    }
    // no backtracking: once skipped or taken, the decision is final
  }

  return result;
}

Alternative Approaches

• When greedy fails, use DP instead: coin change with arbitrary denominations is the textbook counterexample: always taking the largest coin (greedy) fails for coin systems like [1, 3, 4] when making change for 6 (greedy gives 4+1+1=3 coins, but 3+3=2 coins is better), so it requires full DP over all denominations.
• Exchange argument vs. induction proof: some greedy proofs are easiest via an exchange argument (show any optimal solution can be transformed into the greedy one without getting worse); others are easiest via induction on prefix optimality.
• Greedy + heap: problems like Task Scheduler or meeting-room scheduling often combine a greedy strategy with a priority queue to always pick the "most urgent" remaining item efficiently.
• Two-pointer greedy: some greedy problems (like Gas Station) can be solved with a single running total and a reset point instead of a sort, which is even more efficient than sort-based greedy.

Common Mistakes

• Assuming greedy works without checking: the most common interview mistake is applying a greedy strategy to a problem that actually requires DP (like general coin change) because the greedy answer "looks" right on small examples.
• Sorting by the wrong key: interval problems are notorious for this: sorting by start time instead of end time (or vice versa) can silently produce a suboptimal answer.
• Forgetting ties need a secondary rule: when two items have the same primary sort key, an unspecified tie-break can flip the answer for edge cases.
• Not resetting running state correctly: Gas Station and Jump Game both require careful reset logic when the running total goes negative or a reachable-index tracker needs updating.
• Off-by-one when counting removals vs. keeps: Non-overlapping Intervals asks for the count removed, which is easy to accidentally compute as the count kept or vice versa.

Pattern Summary

Greedy algorithms trade the safety of exploring every option for the speed of a single decisive pass, and that trade is only valid when you can prove the local choice never harms the global optimum. Sort by the key that exposes the safe choice, walk through once, and never revisit a decision; the moment you can't justify why the local choice is safe, that's the signal to fall back to dynamic programming instead.