DSA Greedy Algorithms
Explore greedy algorithms — strategies that make the locally optimal choice at each step — and learn when that approach is guaranteed to work and when it silently fails.
What Is a Greedy Algorithm?
A greedy algorithm builds a solution step by step, at each step choosing whichever option looks best right now, without reconsidering earlier choices or looking ahead. Greedy algorithms are simple and fast, but they only produce a truly optimal answer when the problem has a special structure called the greedy-choice property: a locally optimal choice at each step is guaranteed to lead to a globally optimal solution.
- Greedy-choice property - a locally optimal choice at each step leads to a globally optimal solution
- Optimal substructure - an optimal solution to the problem contains optimal solutions to its subproblems
- No backtracking - once a choice is made, a greedy algorithm never revisits or undoes it
- Not always optimal - without the greedy-choice property, a greedy strategy can produce a suboptimal or even wrong answer
When Greedy Works: Coin Change and Activity Selection
Two classic problems where the greedy-choice property holds are coin change with canonical denominations and activity selection. In coin change, repeatedly taking the largest coin that does not exceed the remaining amount never blocks a better solution. In activity selection — choosing the maximum number of non-overlapping intervals from a schedule — always picking the activity that finishes earliest leaves the most room for future choices.
Example
def greedy_coin_change(amount, coins):
coins = sorted(coins, reverse=True)
result = []
for coin in coins:
while amount >= coin:
amount -= coin
result.append(coin)
return result
print(greedy_coin_change(63, [25, 10, 5, 1])) # [25, 25, 10, 1, 1, 1]Example
def select_activities(activities):
# Each activity is a (start, end) tuple.
activities = sorted(activities, key=lambda a: a[1])
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
schedule = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print(select_activities(schedule)) # [(1, 4), (5, 7), (8, 9)]When Greedy Fails: Non-Canonical Coins
Greedy coin change breaks down for arbitrary denominations. With coins [1, 3, 4] and a target of 6, greedy takes the largest coin first (4), then is forced into two 1-coins, using 3 coins total — but the optimal answer is 3 + 3, using only 2 coins. Greedy can't see that taking a smaller coin now would have led to a better outcome later.
Example
def greedy_coin_change(amount, coins):
coins = sorted(coins, reverse=True)
result = []
for coin in coins:
while amount >= coin:
amount -= coin
result.append(coin)
return result
# Greedy picks 4 + 1 + 1 (3 coins), but 3 + 3 (2 coins) is optimal.
print(greedy_coin_change(6, [1, 3, 4])) # [4, 1, 1] -- not optimal!Exercise: DSA Greedy Algorithms
What is the core strategy of a greedy algorithm?
