75 questions using this pattern
Make locally optimal choices at each step, hoping to find a global optimum. Greedy algorithms are simple and efficient but only work when the problem has the greedy choice property—local optima lead to global optimum.
Imagine eating at a buffet where you can only fill your plate once. The greedy strategy: always take the food that looks most appealing right now. This works if what looks best now is actually best overall—but fails if you fill up on appetizers and miss the main course.
Another analogy: making change with the fewest coins. For US currency, always using the largest coin that fits (quarter before dime before nickel) gives optimal results. But with coins [1, 3, 4], making 6 cents: greedy gives 4+1+1=3 coins, while optimal is 3+3=2 coins.
Greedy algorithms work by making the choice that seems best at each step without reconsidering previous choices. This works when:
Greedy choice property: A locally optimal choice is part of some globally optimal solution.
Optimal substructure: After making a greedy choice, the remaining subproblem has the same structure as the original.
The key insight is recognizing when greedy works. Common patterns:
When greedy doesn't work (like 0/1 Knapsack), use dynamic programming instead.
def can_jump(nums: list[int]) -> bool: max_reach = 0 for i in range(len(nums)): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) return TrueGiven nums = [2, 3, 1, 1, 4], can we reach the last index? Each value tells us the maximum jump length from that position.
Activity Selection (maximize non-overlapping activities):
Activities: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11)]
Sort by end time: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11)]
Greedy selection:
- (1,4): Select ✓ (first activity)
- (3,5): Skip ✗ (overlaps with (1,4))
- (0,6): Skip ✗ (overlaps)
- (5,7): Select ✓ (starts after 4)
- (3,9): Skip ✗ (overlaps)
- (5,9): Skip ✗ (overlaps)
- (6,10): Skip ✗ (overlaps with (5,7))
- (8,11): Select ✓ (starts after 7)
Selected: [(1,4), (5,7), (8,11)] — 3 activities
Why sort by end time?
Intuition: Finishing early leaves maximum room for future activities.
If we picked an activity ending later but overlapping with one ending earlier:
- We'd block the same activities (both overlap with them)
- But we'd also potentially block more future activities
- So the earlier-ending activity is never worse
Jump Game (can reach end?):
Array: [2, 3, 1, 1, 4]
Greedy: Track farthest reachable position
i=0: farthest = max(0, 0+2) = 2
i=1: farthest = max(2, 1+3) = 4 ← can reach end!
i=2: farthest = max(4, 2+1) = 4
i=3: farthest = max(4, 3+1) = 4
i=4: reached end ✓
Use this skeleton as a starting point for problems using this pattern:
def activity_selection(activities: list[tuple[int, int]]) -> list[tuple]:
"""Select maximum non-overlapping activities."""
# Sort by end time
activities.sort(key=lambda x: x[1])
result = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end: # No overlap
result.append((start, end))
last_end = end
return result
def can_jump(nums: list[int]) -> bool:
"""Check if you can reach the last index."""
farthest = 0
for i in range(len(nums)):
if i > farthest:
return False # Can't reach this position
farthest = max(farthest, i + nums[i])
return True
def min_jumps(nums: list[int]) -> int:
"""Minimum jumps to reach the last index."""
if len(nums) <= 1:
return 0
jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumps
def fractional_knapsack(capacity: int,
items: list[tuple[int, int]]) -> float:
"""Maximum value with fractional items. Items are (value, weight)."""
# Sort by value-to-weight ratio (descending)
items.sort(key=lambda x: x[0] / x[1], reverse=True)
total_value = 0
for value, weight in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
# Take fraction of this item
total_value += value * (capacity / weight)
break
return total_value
def min_meeting_rooms(intervals: list[list[int]]) -> int:
"""Minimum meeting rooms needed."""
events = []
for start, end in intervals:
events.append((start, 1)) # Start event
events.append((end, -1)) # End event
events.sort()
rooms = 0
max_rooms = 0
for _, delta in events:
rooms += delta
max_rooms = max(max_rooms, rooms)
return max_rooms
def partition_labels(s: str) -> list[int]:
"""Partition string so each letter appears in at most one part."""
last = {c: i for i, c in enumerate(s)}
partitions = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # Extend partition to include all of char c
if i == end: # Reached end of partition
partitions.append(end - start + 1)
start = i + 1
return partitions
def gas_station(gas: list[int], cost: list[int]) -> int:
"""Find starting station to complete circuit."""
total_surplus = 0
current_surplus = 0
start = 0
for i in range(len(gas)):
total_surplus += gas[i] - cost[i]
current_surplus += gas[i] - cost[i]
if current_surplus < 0:
# Can't reach next station from current start
start = i + 1
current_surplus = 0
return start if total_surplus >= 0 else -1Look for these keywords and patterns in problem descriptions:
Not all optimization problems have the greedy choice property. Using greedy on 0/1 Knapsack or Coin Change (with arbitrary coins) gives suboptimal results.
Fix:
Verify greedy works by proving the greedy choice property, or test against known cases. When in doubt, use dynamic programming.
Sorting by the wrong attribute (e.g., start time instead of end time for activity selection) leads to suboptimal selections.
Fix:
Think about what greedy property you're exploiting. For "maximize activities," ending early maximizes remaining time. For "minimize lateness," sorting by deadline helps.
Select maximum non-overlapping intervals. Sort by end time, greedily select if no overlap with previous.
Examples: Activity Selection, Non-overlapping Intervals
Track farthest reachable position, greedily extend reach.
Examples: Jump Game, Jump Game II, Video Stitching
Match items greedily based on some criteria (smallest to smallest, largest to largest, etc.).
Examples: Assign Cookies, Boats to Save People
Schedule tasks to minimize lateness or maximize throughput. Often involves sorting by deadline or duration.
Examples: Task Scheduler, Meeting Rooms, Car Pooling
Greedily merge two lowest-frequency nodes to build optimal prefix-free encoding tree.
Examples: Huffman Coding (not on LeetCode, but classic)
Start here to build foundational understanding.
Master the pattern with these representative problems.
Test your mastery with complex variations.
Explore similar techniques:
Break problems into overlapping subproblems, storing results to avoid recomputation. This transforms exponential time complexity into polynomial by trading space for time.
Process and manipulate intervals (ranges) that may share common regions. The key insight is that sorting intervals by start time allows efficient detection and handling of overlaps through a single linear pass.
Empty input, single element, or already-solved cases often need special handling.
Fix:
Check for edge cases before main algorithm:
if not items:
return 0
if len(items) == 1:
return items[0]
Sometimes greedy works forward but not backward (or vice versa). Processing in the wrong order gives wrong results.
Fix:
Consider both directions. For interval problems, usually sort by end time and process forward. For some problems, working backward reveals the greedy choice more clearly.