A
AiTechWorlds
AiTechWorlds
A hiker is navigating a mountain trail using only one rule: at every junction, take the path that looks best right now. No map, no planning ahead, no backtracking. Just the immediate best choice.
Sometimes this strategy leads to the summit. Sometimes it leads to a dead end. Whether it works depends entirely on the landscape.
That's greedy thinking: at each decision point, make the locally optimal choice, trusting that the sequence of local bests will produce a global best.
The fascinating challenge in algorithm design is figuring out when this trust is warranted — and when it's a trap.
A greedy algorithm makes the best available choice at each step, never reconsidering past decisions. It's fast and simple, but it requires a proof that local optimality implies global optimality.
Two conditions for a valid greedy solution:
The difference from DP: greedy commits to a choice permanently. DP explores all options.
For standard coin denominations (1, 5, 10, 25 cents in US currency), greedy works perfectly: always pick the largest coin that fits.
def coin_change_greedy(coins, amount):
coins = sorted(coins, reverse=True) # Sort descending: largest first
result = []
for coin in coins:
while amount >= coin: # Use this coin as many times as possible
result.append(coin)
amount -= coin
return result if amount == 0 else None
# --- Example ---
coins = [25, 10, 5, 1]
amount = 41
selected = coin_change_greedy(coins, amount)
print(f"Coins selected: {selected}")
print(f"Total coins: {len(selected)}")
Output:
Coins selected: [25, 10, 5, 1]
Total coins: 4
41 cents = 25 + 10 + 5 + 1
Important caveat: Greedy fails for arbitrary denominations. With coins [1, 6, 10] and amount 12:
For arbitrary denominations, you need DP (as covered in Lesson 4).
Problem: You have a meeting room that can hold one meeting at a time. Given a list of meetings with start and end times, schedule the maximum number of non-overlapping meetings.
def activity_selection(activities):
"""
activities = [(start, end, name)]
Returns the maximum set of non-overlapping activities.
"""
# Sort by END time — this is the greedy insight
sorted_acts = sorted(activities, key=lambda x: x[1])
selected = [sorted_acts[0]] # Always take the first (earliest end)
for act in sorted_acts[1:]:
last_end = selected[-1][1] # End time of last selected activity
if act[0] >= last_end: # New activity starts after last ends
selected.append(act)
return selected
# --- Example: 8 meetings ---
meetings = [
(9, 10, "Team Standup"),
(9, 12, "Project Review"),
(11, 12, "Client Call"),
(10, 11, "Design Review"),
(12, 14, "Lunch Interview"),
(13, 15, "Budget Meeting"),
(14, 16, "One-on-One"),
(15, 17, "Sprint Planning")
]
selected = activity_selection(meetings)
print("Selected meetings:")
for start, end, name in selected:
print(f" {start:02d}:00 - {end:02d}:00 {name}")
print(f"\nTotal meetings scheduled: {len(selected)} out of {len(meetings)}")
Output:
Selected meetings:
09:00 - 10:00 Team Standup
10:00 - 11:00 Design Review
11:00 - 12:00 Client Call
12:00 - 14:00 Lunch Interview
14:00 - 16:00 One-on-One
Total meetings scheduled: 5 out of 8
Why sort by end time? Choosing the meeting that ends soonest leaves maximum room for future meetings. This is the greedy choice property: earliest finish time = locally optimal = globally optimal (provable by exchange argument).
Timeline visualization:
9 10 11 12 13 14 15 16 17
|====| Team Standup
|=========| Project Review (skipped — ends too late)
|====| Design Review
|===| Client Call
|======| Lunch Interview
|=====| Budget Meeting (skipped — starts too early)
|======| One-on-One
|======| Sprint Planning (skipped)
Problem: Encode text to minimize storage size. Characters that appear frequently should get shorter bit codes; rare characters can have longer codes.
Real use: JPEG, MP3, ZIP, and HTTP compression all use variants of Huffman coding.
import heapq
from collections import Counter
def huffman_codes(text):
freq = Counter(text) # Count character frequencies
# Build min-heap: (frequency, character)
heap = [[freq, char] for char, freq in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
# Greedy: always merge the two least frequent nodes
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
# New internal node: combined frequency, children are lo and hi
heapq.heappush(heap, [lo[0] + hi[0], lo, hi])
def generate_codes(node, prefix="", codes={}):
if isinstance(node[1], str): # Leaf node = actual character
codes[node[1]] = prefix or "0"
return
generate_codes(node[1], prefix + "0", codes) # Left branch = "0"
generate_codes(node[2], prefix + "1", codes) # Right branch = "1"
return codes
return generate_codes(heap[0])
# --- Example ---
text = "aabbbccccdddddeeeeeee"
codes = huffman_codes(text)
print("Character | Frequency | Huffman Code | Bits")
print("-" * 45)
freq = Counter(text)
for char in sorted(codes, key=lambda c: freq[c], reverse=True):
bits_used = freq[char] * len(codes[char])
print(f" '{char}' | {freq[char]} | {codes[char]:<12} | {bits_used}")
total_bits = sum(freq[c] * len(codes[c]) for c in codes)
naive_bits = len(text) * 8
print(f"\nHuffman encoding: {total_bits} bits")
print(f"Fixed 8-bit ASCII: {naive_bits} bits")
print(f"Space saved: {naive_bits - total_bits} bits ({100*(naive_bits-total_bits)//naive_bits}%)")
Output (approximate):
Character | Frequency | Huffman Code | Bits
---------------------------------------------
'e' | 7 | 10 | 14
'd' | 5 | 00 | 10
'c' | 4 | 110 | 12
'b' | 3 | 1110 | 12
'a' | 2 | 1111 | 8
Huffman encoding: 56 bits
Fixed 8-bit ASCII: 168 bits
Space saved: 112 bits (66%)
Frequent characters get short codes (e=2 bits, d=2 bits). Rare characters get long codes (a=4 bits). Net result: 66% space savings.
Unlike the 0/1 Knapsack (Lesson 4), here you can take fractions of items. This makes greedy optimal.
def fractional_knapsack(items, capacity):
"""
items = [(value, weight, name)]
Returns maximum value achievable within capacity.
"""
# Greedy: take items with highest value-per-weight ratio first
items_sorted = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
total_value = 0
for value, weight, name in items_sorted:
if capacity <= 0:
break
take = min(weight, capacity) # Take as much as possible
fraction = take / weight
total_value += value * fraction
capacity -= take
print(f"Take {fraction*100:.0f}% of {name}: +${value*fraction:.1f}")
return total_value
# --- Example ---
items = [(60, 10, "Gold dust"), (100, 20, "Silver bars"), (120, 30, "Copper ingots")]
capacity = 50
print("Fractional Knapsack:")
max_value = fractional_knapsack(items, capacity)
print(f"Maximum value: ${max_value:.1f}")
Output:
Fractional Knapsack:
Take 100% of Gold dust: +$60.0
Take 100% of Silver bars: +$100.0
Take 67% of Copper ingots: +$80.0
Maximum value: $240.0
With the exact same items, if you cannot split them (0/1 Knapsack):
Items: Gold (value=60, weight=10), Silver (100, 20), Copper (120, 30)
Capacity: 50
Greedy by ratio: Gold + Silver = 60+100 = $160, uses 30kg, 20kg wasted
Optimal (DP): Silver + Copper = 100+120 = $220, uses all 50kg
Greedy gets $160. The optimal is $220. Greedy fails by 27%.
Why? When you can't take fractions, the highest-ratio item might waste capacity. DP considers all combinations; greedy doesn't.
| Factor | Greedy | Dynamic Programming |
|---|---|---|
| Decision revocable? | No | Yes (tries all options) |
| Proof required | Yes (greedy choice property) | Not needed |
| Time complexity | Usually O(n log n) | Often O(n²) or O(n·W) |
| Space | O(1) to O(n) | O(n) to O(n²) |
| Coin change (standard) | Works | Works (overkill) |
| Coin change (arbitrary) | May fail | Always correct |
| Activity selection | Works | Works (overkill) |
| 0/1 Knapsack | May fail | Always correct |
| Fractional Knapsack | Works | Works (overkill) |
| Shortest path | Dijkstra (greedy) works | Bellman-Ford for negatives |
Rule of thumb: Try greedy first. If you can prove local optimal = global optimal, use it. If counterexamples exist, fall back to DP.
Greedy algorithm questions test your ability to:
Common interview greedy problems:
The deeper lesson: greedy algorithms are a mindset, not a recipe. The skill is knowing when local best choices lead to global best outcomes — and having the mathematical intuition to tell the difference.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises