Topics

Greedy Algorithms: A Study Guide

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now and never reconsidering it. When the problem has the right structure, that shortsighted strategy still lands on the global optimum, and it does so far faster than exhaustive search. The catch is that greedy is only correct for some problems, and proving which is the real skill.

Why Greedy Matters#

Greedy algorithms are the fastest tool in the box when they apply: usually O(n log n) dominated by a sort, sometimes O(n). Activity selection, Huffman coding, Dijkstra’s and Prim’s algorithms, interval scheduling, and many coin and jump problems are greedy. Interviewers use greedy questions to see whether you can justify a strategy rather than just code one, because the wrong greedy choice fails silently on an edge case.

When Greedy Works#

Two properties must hold:

  • Greedy choice property. A globally optimal solution can be reached by making a locally optimal choice at each step.
  • Optimal substructure. An optimal solution to the whole contains optimal solutions to its subproblems.

When only the second holds, you usually need dynamic programming instead, which reconsiders choices. Coin change is the cautionary tale: greedy works for standard currency but fails for arbitrary coin sets, where DP is required.

Complexity#

Most greedy algorithms sort the input, then make one linear pass:

StepTime
Sort by the greedy keyO(n log n)
Single greedy passO(n)
OverallO(n log n)

A Short Example#

Interval scheduling: to fit the most non-overlapping meetings, always pick the one that finishes earliest.

1def max_meetings(intervals):
2    intervals.sort(key=lambda iv: iv[1])   # sort by end time
3    count, last_end = 0, float("-inf")
4    for start, end in intervals:
5        if start >= last_end:              # no overlap
6            count += 1
7            last_end = end
8    return count

Common Pitfalls#

  • Assuming greedy is correct without proof. The most common failure. If you cannot argue the greedy-choice property, reach for DP.
  • Sorting by the wrong key. In interval scheduling, sorting by start time instead of end time gives a wrong answer. The key is the whole strategy.
  • Ignoring counterexamples. Test the classic trap: does your greedy coin change work for coins like [1, 3, 4] and target 6?
  • Confusing greedy with DP. They look similar; greedy commits, DP explores. Know which one the problem needs.

Where the Curriculum Covers This#

In the 60-day challenge: