Greedy Algorithm

How greedy algorithms work

A greedy algorithm has three components:

1. A choice function — given the current state, what's the locally best next step?
2. A feasibility check — does this choice keep the problem solvable?
3. A termination condition — when have we built a complete solution?

The pattern is "while the problem isn't solved: make the greedy choice, commit, repeat." No backtracking, no reconsidering. The simplicity is what makes greedy fast — and what makes it dangerous when the greedy choice property doesn't hold.

When greedy works (and when it fails)

Three problems, three different stories:

Problem	Greedy strategy	Optimal?	Why
Coin change (US coins: 1, 5, 10, 25)	Largest coin ≤ remaining	Yes	Coin denominations have the canonical property that no smaller-coin combo beats the larger one
Coin change (arbitrary: 1, 3, 4)	Largest coin ≤ remaining	No	Greedy on 6 picks [4, 1, 1]; DP optimal is [3, 3]
Activity selection	Earliest end time first	Yes	Exchange argument: any optimal can be transformed to greedy without loss
0/1 knapsack	Best value/weight ratio	No	Discrete items: greedy may pick one big item when two smaller ones would have higher value
Fractional knapsack	Best value/weight ratio	Yes	Fractions allow optimal trade-offs at the boundary
Minimum spanning tree	Smallest non-cycling edge	Yes	Cut property of MSTs — proven via exchange
Huffman coding	Merge two lowest-frequency nodes	Yes	Standard exchange argument on optimal prefix codes
Longest path in general graph	Various	No	NP-hard — greedy can't even approximate well

If you can't prove the greedy choice property, fall back to DP. If your greedy passes a few hand-picked examples but you're not sure why, build adversarial test cases — coin change (1, 3, 4) on 6 is the canonical adversary that breaks naive greedy thinking.

Greedy vs dynamic programming

	Greedy	Dynamic programming
Decision policy	Locally optimal — commit	Consider all options — pick best after
Time	O(n) or O(n log n) typical	O(n²) or O(n × k) typical
Space	O(1) typical	O(n) or O(n × k) for the table
Backtracking	Never	Implicit — the table considers all paths
Required property	Greedy choice property	Overlapping subproblems
Failure mode	Wrong answer, silently	Slower, may be unnecessary
Always correct?	Only if greedy choice property holds	Yes (when properties match)

Try greedy first — if you can prove correctness, the resulting algorithm is simpler and faster. If you can't prove it, or you find a counter-example, fall back to DP.

Famous greedy algorithms

Activity Selection

Given n activities with start and end times, find the maximum non-overlapping subset.

function activitySelection(activities) {
  // Sort by end time
  activities.sort((a, b) => a.end - b.end);
  const selected = [activities[0]];
  let lastEnd = activities[0].end;
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }
  return selected;
}

O(n log n) for the sort, O(n) for the scan. The proof: any optimal solution either includes the earliest-ending activity, or it can be modified to include it without losing count — exchange argument.

Huffman Coding

Build a prefix code where common characters get short codes and rare ones get long codes. Greedy strategy: repeatedly merge the two lowest-frequency nodes into a new node whose frequency is their sum.

function huffmanTree(freqs) {
  // freqs: Map of character -> frequency
  const heap = new MinHeap();
  for (const [char, freq] of freqs) heap.push({ char, freq, left: null, right: null });

  while (heap.size() > 1) {
    const a = heap.pop();
    const b = heap.pop();
    heap.push({ char: null, freq: a.freq + b.freq, left: a, right: b });
  }
  return heap.pop(); // root of the Huffman tree
}

Used in DEFLATE (zip, gzip), JPEG, MP3. The greedy choice — merge lowest two — provably builds an optimal prefix code by exchange argument.

Fractional Knapsack

function fractionalKnapsack(items, capacity) {
  // items: [{value, weight}]
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  let total = 0;
  for (const item of items) {
    if (capacity >= item.weight) {
      total += item.value;
      capacity -= item.weight;
    } else {
      total += item.value * (capacity / item.weight);
      break;
    }
  }
  return total;
}

When to reach for greedy

• Optimization problems with a clear "best" local choice. Activity selection, fractional knapsack, MST, shortest path with non-negative weights.
• Approximation algorithms for NP-hard problems. Greedy set cover gives an O(log n)-approximation, the best polynomial-time achievable. Greedy max-cut gives a 1/2-approximation.
• Online algorithms. When you must decide now without seeing future inputs (cache eviction, online scheduling), greedy choices are forced — no backtracking is even possible.
• Constructive heuristics. When optimal isn't required but a good answer fast matters — packing, bin packing, route construction in vehicle routing.

How to prove a greedy works

1. Identify the greedy choice. What's the locally best step?
2. State the greedy choice property. "Some optimal solution makes this greedy choice first."
3. Prove it via exchange. Assume an optimal solution differs from greedy. Show you can swap one element of the optimal for the greedy choice without making it worse. By induction, greedy = optimal.
4. State the optimal substructure. After making the greedy choice, what remains is a smaller version of the same problem.
5. Recurse. The recursion gives an inductive proof that greedy on the whole problem is optimal.

If any step gets stuck, your greedy may not be correct. Construct an adversarial input — coin change (1, 3, 4) on 6 is a great template — to verify.

Common bugs and edge cases

• Confusing "intuitively right" with "provably correct." Greedy strategies that feel right often fail on adversarial inputs. Always test edge cases.
• Sorting by the wrong key. Activity selection sorted by start time gives wrong answers. Sort by end time. Knapsack sorted by absolute value (not value/weight ratio) is also wrong.
• Ignoring the feasibility check. The greedy choice must keep the remaining problem solvable. For activity selection: only pick if it doesn't overlap with prior picks. Skipping the check produces invalid solutions.
• Trying greedy on 0/1 knapsack. Doesn't work — needs DP. Easy to confuse with fractional knapsack which IS greedy. Discrete vs continuous is the distinguishing feature.
• Assuming greedy is always faster than DP. Greedy with a sort is O(n log n); some DP solutions are O(n). Profile before assuming.