Greedy Algorithms Explained
A greedy algorithm builds a solution step by step, and at every step it makes the choice that looks best right now — without ever going back to reconsider an earlier decision. That sounds risky, and sometimes it is: greedy strategies don’t work for every problem. But for a specific, well-understood class of problems, the locally best choice at each step really does add up to the globally best overall solution, and when that’s true, greedy algorithms are usually simpler and faster than dynamic programming. This lesson covers how to recognize that class of problems, how to convince yourself a greedy strategy works, and how it fails when it doesn’t.
Overview: How Greedy Algorithms Work
Imagine you’re scheduling a single conference room and you have a list of meeting requests, each with a start and an end time. You can’t accept every request — many overlap — so you want to accept as many non-overlapping meetings as possible. One instinct is to accept whichever meeting starts earliest. Another is to accept the shortest meeting first, hoping to leave the most room for others. Neither of those turns out to be optimal — but a third rule, always accept whichever remaining meeting ends soonest, is provably optimal. That’s a greedy algorithm: at each step, apply a simple local rule (pick the earliest finishing time) and never revisit the decision, yet the sequence of choices adds up to a solution that is globally best.
A problem is a good candidate for a greedy algorithm when it has two properties:
- Greedy-choice property — a globally optimal solution can be reached by making a sequence of locally optimal (greedy) choices. Choosing the best option available right now never rules out reaching the overall best answer later.
- Optimal substructure — an optimal solution to the problem contains optimal solutions to its subproblems. (This is the same property dynamic programming relies on; the difference is that DP considers every subproblem and combines results, while greedy commits to one choice per step and never looks back.)
When both properties hold, greedy algorithms are usually much faster than dynamic programming, because there’s no need to explore multiple subproblems or store a table of intermediate results — you make one pass, picking the best option at each step. When either property fails, a greedy strategy still produces a solution — it just isn’t guaranteed to be the best one — and there’s no substitute for dynamic programming or exhaustive search. Recognizing which situation you’re in is the real skill this lesson teaches; the code for a greedy algorithm is almost always short, but the hard part is knowing it’s correct.
Classic examples where greedy is provably optimal include activity/interval selection, fractional knapsack, Huffman coding, Kruskal’s and Prim’s algorithms for minimum spanning trees, Dijkstra’s shortest-path algorithm (with non-negative edge weights), and making change with a canonical coin system like U.S. currency. Classic traps where a greedy strategy looks tempting but fails include the 0/1 knapsack problem (you can’t take a fraction of an item, so the ratio-based rule from fractional knapsack breaks down) and making change with arbitrary, non-canonical denominations.
Time and Space Complexity
Nearly every greedy algorithm follows the same shape: sort the input by some criterion, then make one linear pass over it, greedily accepting or rejecting each element. That shape drives the complexity:
| Algorithm | Time | Space | Why |
|---|---|---|---|
| Activity selection | O(n log n) |
O(n) |
Sorting n activities by finish time costs O(n log n); the follow-up scan that greedily accepts non-overlapping activities is a single O(n) pass. The sort dominates. |
| Fractional knapsack | O(n log n) |
O(n) |
Sorting n items by value-to-weight ratio costs O(n log n); filling the knapsack afterward is a single O(n) pass. |
| Greedy coin change (canonical system) | O(d + c) |
O(c) |
d is the (small, fixed) number of denominations and c is the number of coins the result actually contains, which bounds the inner while loop. |
The space cost is usually just the output (the selected activities, the coins used) plus, if you sort indices rather than the objects themselves, an O(n) array of indices. Some greedy algorithms — Dijkstra’s algorithm and Huffman coding, for example — use a heapq min-heap to repeatedly extract the next-best choice in O(log n) instead of re-scanning the remaining items in O(n) each time; that’s what keeps those algorithms at O(n log n) or O(E log V) overall instead of a slower O(n²).
Examples
Example 1: Activity Selection
Given a list of activities with start and finish times, select the maximum number of non-overlapping activities. The greedy rule: sort by finish time, then repeatedly take the next activity whose start time is not earlier than the finish time of the last accepted activity.
def activity_selection(start: list[int], finish: list[int]) -> list[int]:
activities = sorted(range(len(start)), key=lambda i: finish[i])
selected = [activities[0]]
last_finish = finish[activities[0]]
for i in activities[1:]:
if start[i] >= last_finish:
selected.append(i)
last_finish = finish[i]
return selected
def main() -> None:
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
selected = activity_selection(start, finish)
print("Selected activity indices:", selected)
for i in selected:
print(f"Activity {i}: start={start[i]}, finish={finish[i]}")
main()Output:
Selected activity indices: [0, 1, 3, 4]
Activity 0: start=1, finish=2
Activity 1: start=3, finish=4
Activity 3: start=5, finish=7
Activity 4: start=8, finish=9Tracing through it: sorting by finish time happens to leave the indices in their original order here, since finish = [2, 4, 6, 7, 9, 9] is already non-decreasing. The scan starts by accepting activity 0 (finish 2). Activity 1 starts at 3, which is not before 2, so it’s accepted (finish becomes 4). Activity 2 starts at 0, which is before 4, so it’s skipped — it would overlap. Activity 3 starts at 5, not before 4, so it’s accepted (finish becomes 7). Activity 4 starts at 8, not before 7, so it’s accepted (finish becomes 9). Activity 5 starts at 5, which is before 9, so it’s skipped. The result — four non-overlapping activities — is the maximum possible for this input.
Example 2: Fractional Knapsack
You have a knapsack with a weight capacity and a set of items, each with a weight and a value. Unlike the 0/1 knapsack problem, here you’re allowed to take a fraction of an item. The greedy rule: always take as much as possible of the item with the highest value-to-weight ratio first.
def fractional_knapsack(weights: list[float], values: list[float], capacity: float) -> float:
items = sorted(range(len(weights)), key=lambda i: values[i] / weights[i], reverse=True)
total_value = 0.0
remaining = capacity
for i in items:
if remaining <= 0:
break
take = min(weights[i], remaining)
fraction = take / weights[i]
total_value += fraction * values[i]
remaining -= take
return total_value
def main() -> None:
weights = [10, 20, 20]
values = [60, 100, 80]
capacity = 40
max_value = fractional_knapsack(weights, values, capacity)
print(f"Maximum value in knapsack: {max_value}")
main()Output:
Maximum value in knapsack: 200.0Tracing through it: the ratios are 60/10 = 6.0, 100/20 = 5.0, and 80/20 = 4.0, so the items are already in the right order. With 40 units of capacity, the first item (weight 10) is taken whole, leaving 30 capacity and a running value of 60.0. The second item (weight 20) is also taken whole, leaving 10 capacity and a running value of 160.0. Only 10 of the third item’s 20 units of weight fit, so half of it (fraction 0.5) is taken, adding 0.5 × 80 = 40.0 to the total, for a final value of 200.0. This ratio-based greedy rule is only valid because fractional items are allowed — for the 0/1 knapsack, where each item must be taken whole or not at all, the same rule does not produce an optimal answer, and you need dynamic programming instead.
Example 3: Making Change Greedily
Given a set of coin denominations and a target amount, use as few coins as possible. The greedy rule: always use the largest denomination that still fits. This works correctly for a canonical coin system such as U.S. currency (1, 5, 10, 25 cent coins), but — as the Common Mistakes section below shows — it is not guaranteed to work for arbitrary denominations.
def make_change_greedy(amount: int, denominations: list[int]) -> list[int]:
denominations = sorted(denominations, reverse=True)
change = []
remaining = amount
for coin in denominations:
while remaining >= coin:
change.append(coin)
remaining -= coin
return change
def main() -> None:
denominations = [25, 10, 5, 1]
amount = 63
coins_used = make_change_greedy(amount, denominations)
print(f"Coins used for {amount} cents: {coins_used}")
print(f"Total coins: {len(coins_used)}")
main()Output:
Coins used for 63 cents: [25, 25, 10, 1, 1, 1]
Total coins: 6Tracing through it: with 63 cents remaining, two 25-cent coins are taken (50 cents used, 13 remaining). No more 25s fit. One 10-cent coin is taken (13 becomes 3). No 5-cent coin fits into 3 cents, so three 1-cent coins are taken. Total: six coins — the fewest coins possible for 63 cents using U.S. denominations.
How It Works, Step by Step
Let’s trace the activity-selection greedy algorithm one decision at a time on the same input as Example 1: start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9].
| Step | Activity (start, finish) | Compared against last accepted finish | Decision |
|---|---|---|---|
| 1 | 0: (1, 2) | first activity, nothing to compare | Accept — last finish becomes 2 |
| 2 | 1: (3, 4) | start 3 is not less than 2 | Accept — last finish becomes 4 |
| 3 | 2: (0, 6) | start 0 is less than 4 | Reject — overlaps activity 1 |
| 4 | 3: (5, 7) | start 5 is not less than 4 | Accept — last finish becomes 7 |
| 5 | 4: (8, 9) | start 8 is not less than 7 | Accept — last finish becomes 9 |
| 6 | 5: (5, 9) | start 5 is less than 9 | Reject — overlaps activity 4 |
Notice the algorithm never reconsiders activity 2 or activity 5 once they’re rejected, and it never un-accepts activity 0 or activity 1 to check whether a different combination might do better. That’s the defining feature of a greedy algorithm — one forward pass, one irreversible decision per step — and it’s only correct here because sorting by finish time guarantees that whichever activity finishes soonest can always be safely included in some optimal solution.
Common Mistakes
Mistake 1: Assuming Greedy Always Gives the Optimal Answer
The make_change_greedy function from Example 3 works for U.S. coins, but it silently gives a wrong (non-optimal) answer for other denomination sets. It’s tempting to reuse the same code and assume it always works:
def make_change_greedy(amount: int, denominations: list[int]) -> list[int]:
denominations = sorted(denominations, reverse=True)
change = []
remaining = amount
for coin in denominations:
while remaining >= coin:
change.append(coin)
remaining -= coin
return change
def main() -> None:
denominations = [4, 3, 1]
amount = 6
coins_used = make_change_greedy(amount, denominations)
print(f"Greedy result: {coins_used}")
print(f"Greedy coin count: {len(coins_used)}")
main()Output:
Greedy result: [4, 1, 1]
Greedy coin count: 3Tracing through it: with 6 cents remaining and denominations sorted as [4, 3, 1], the greedy rule grabs the 4 first (2 remaining), then can’t use a 3 (2 is less than 3), so it falls back to two 1-coins — three coins total. But two 3-coins would cover the same 6 cents in only two coins, the actual optimal answer. Greedily taking the biggest coin that fits is only guaranteed optimal for canonical coin systems. For arbitrary denominations, use dynamic programming (a bottom-up minimum-coins-per-amount table) instead, since it considers every combination rather than committing early.
Mistake 2: Mutable Default Arguments in Accumulator Functions
Greedy algorithms often build up a result list across a loop, and it’s tempting to give that accumulator list a default value directly in the function signature:
def collect_positive(items: list[int], acc: list[int] = []) -> list[int]:
for item in items:
if item > 0:
acc.append(item)
return acc
def main() -> None:
first_result = collect_positive([1, -2, 3])
second_result = collect_positive([4, 5])
print(f"First call result: {first_result}")
print(f"Second call result: {second_result}")
main()Output:
First call result: [1, 3, 4, 5]
Second call result: [1, 3, 4, 5]That’s almost certainly not what you expected — the first call’s result appears to have grown extra elements it never produced. The bug is that a mutable default argument (acc: list[int] = []) is created once, when the function is defined, not once per call. Every call that doesn’t explicitly pass acc shares and mutates that same list object, so first_result and second_result end up pointing at the identical, fully-accumulated list. The fix is to default to None and create a fresh list inside the function body:
def collect_positive(items: list[int], acc: list[int] | None = None) -> list[int]:
if acc is None:
acc = []
for item in items:
if item > 0:
acc.append(item)
return acc
def main() -> None:
first_result = collect_positive([1, -2, 3])
second_result = collect_positive([4, 5])
print(f"First call result: {first_result}")
print(f"Second call result: {second_result}")
main()Output:
First call result: [1, 3]
Second call result: [4, 5]Now each call starts with its own fresh list, exactly as intended.
Best Practices
- Before trusting a greedy algorithm, convince yourself the problem has both the greedy-choice property and optimal substructure — unlike dynamic programming, greedy doesn’t automatically guarantee optimality just because a solution comes out.
- Sort by the right key first. Most greedy algorithms hinge entirely on choosing the correct ordering criterion (finish time, value-to-weight ratio, deadline, etc.) — get that wrong and the whole algorithm falls apart even though the code still runs.
- Reach for
heapqinstead of repeatedly re-scanning for a min or max when the greedy choice must be re-evaluated many times, as in Dijkstra’s algorithm or Huffman coding — it turns anO(n)re-scan into anO(log n)heap operation. - When a coin system, cost structure, or constraint set isn’t canonical or well-behaved, don’t force a greedy solution — switch to dynamic programming.
- Sanity-check a new greedy algorithm against brute force or DP on several small, hand-traceable inputs before trusting it on real data or in an interview.
- Prefer
collections.defaultdictorCounterfor the grouping and counting steps that commonly show up alongside greedy algorithms, rather than hand-rolling them with plain dictionaries.
Practice Exercises
- Minimum Meeting Rooms. Given a list of meeting intervals (each a start and end time), find the minimum number of rooms required to hold all of them without conflicts. Hint: this is a variant of activity selection — try sorting start times and end times separately and sweeping through both. For intervals
[(0, 30), (5, 10), (15, 20)], the answer is 2 rooms. - Jump Game. Given a list of non-negative integers where each element is the maximum jump length from that position, determine greedily whether you can reach the last index starting from index 0. Hint: track the farthest index reachable so far as you scan left to right; if your current position ever exceeds the farthest-reachable point, you’re stuck.
- When Does Greedy Fail? Using the
make_change_greedyfunction from this lesson, trace by hand what it returns for denominations[1, 7, 10]and amount14. Compare that to the true minimum number of coins. Is the greedy answer optimal here? (Hint: two coins can make 14 with this denomination set.)
Summary
- Greedy algorithms build a solution piece by piece, always choosing whichever option looks best right now, and never reconsider past choices.
- They only produce a truly optimal solution when the problem has both the greedy-choice property and optimal substructure — verify this before trusting the result.
- Correct classic uses: activity selection, fractional knapsack, Huffman coding, canonical coin systems, Dijkstra’s shortest path with non-negative weights, and Kruskal’s/Prim’s minimum spanning tree algorithms.
- Classic traps: 0/1 knapsack and coin change with non-canonical denominations, where a tempting greedy rule produces a plausible but suboptimal answer.
- Complexity is typically
O(n log n)time, driven by an initial sort, withO(n)or better extra space; heap-based variants keep repeated re-selection atO(log n)per step instead ofO(n). - When in doubt, test a greedy strategy against brute force or dynamic programming on small inputs before trusting it in production or an interview.
