Greedy
Make the locally optimal choice at each step, trusting that it leads to a globally optimal solution. Greedy works when two properties hold: (1) greedy choice property — a local optimum is part of a global optimum, and (2) optimal substructure — an optimal solution contains optimal solutions to subproblems. Common in scheduling, interval selection, and jump/reachability problems.
Problem: Jump Game (Greedy)
Given array [2, 3, 1, 1, 4], can you reach the last index? Each element represents max jump length from that position.
i=0: maxReach = max(0, 0+2) = 2
Start at index 0 with value 2. We can reach at most index 0+2=2. Update maxReach = 2.
When to Use
- Activity selection / scheduling
- Jump games / reachability
- Huffman encoding / interval partitioning
- Minimum number of operations
Key Indicators
- Locally optimal leads to global optimum
- Scheduling / activity selection
- Jump / reach / cover problems
- Minimum steps or operations
Complexity
O(n log n) or O(n)
O(1) or O(n)
Common Problems
Code
# Jump Game example:
max_reach = 0
for i in range(n):
if i > max_reach:
return False # can't reach here
max_reach = max(max_reach, i + nums[i])
return TrueWant all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)