Greedy Algorithms
Take the locally best choice and prove it stays globally optimal. When greedy works, and how to know it does.
Greedy algorithms make one local choice, commit to it, and move on. That is the whole appeal: no table, no recursion tree, no revisiting old states. When the problem has the right structure, greedy is the shortest correct solution in the room.
The danger is that “seems best now” is not a proof. A greedy solution works only when a locally optimal choice can always be extended into a globally optimal answer. Your job is to find that property, state it, and defend it.
Dynamic programming keeps multiple futures alive because the next choice depends on hidden history. Greedy collapses those futures into one summary: farthest reach, earliest ending interval, current tank, last required index.
The mental model
A greedy proof usually has an exchange argument. You show that if an optimal solution does not make your greedy choice, you can swap its first choice with yours without making the answer worse. After the swap, the remaining problem has the same shape, so the argument repeats.
The code often looks like a single pass over a carefully chosen ordering:
def greedy_template(items):
items.sort(key=priority)
state = initial_state()
for item in items:
if item_can_extend_answer(item, state):
take(item, state)
else:
repair_or_skip(item, state)
return answer_from(state)For reachability problems, sorting may not even be needed. You scan in input order while maintaining the best frontier seen so far:
def reachable(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return TrueThe invariant is the real solution: after processing index i, farthest is the rightmost position reachable using jumps that start at or before i.
Pattern recognition
Variations
Worked problems
Try each yourself before revealing the solution. The code is short; the proof is where the interview signal lives.
Jump Game
You start at the first index of an array. Each value tells you the maximum number of steps you may jump from that position. Return whether you can reach the final index.
Approach. Track the farthest index reachable so far. If the scan ever reaches an index beyond that frontier, there is no way to stand there and the answer is false. Otherwise, every visited index may extend the frontier. The greedy choice is to keep only the best reach, because shorter reaches are dominated.
Show solution
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return TrueComplexity. O(n) time and O(1) space. The scan visits each index once and the state is just the current farthest reachable position.
Gas Station
There are gas stations arranged in a circle. At station i, you gain gas[i] and spend cost[i] to drive to the next station. Return an index you can start from to complete the circuit, or -1 if no such start exists.
Approach. If total gas is less than total cost, no start can work. Otherwise, scan once with a tentative start. When the tank becomes negative at station i, no station between the tentative start and i can be a valid start: each of them would begin with even less accumulated surplus before the same failure point. So reset the start to i + 1.
Show solution
def can_complete_circuit(gas, cost):
if sum(gas) < sum(cost):
return -1
start = 0
tank = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return startComplexity. O(n) time and O(1) space. The total-sum check proves existence; the reset rule skips impossible starts in one pass.
Partition Labels
Split a string into as many contiguous parts as possible so that each character appears in at most one part. Return the lengths of the parts.
Approach. For each character, record its final index. While scanning a segment, extend the segment’s end to cover the last occurrence of every character you see. Once the scan reaches that end, all obligations inside the segment are closed, so cutting there is safe and maximizes the number of future cuts.
Show solution
def partition_labels(s):
last = {ch: i for i, ch in enumerate(s)}
result = []
start = 0
end = 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
result.append(end - start + 1)
start = i + 1
return resultComplexity. O(n) time and O(k) space, where k is the number of distinct characters. Each character forces the current partition to cover its last position exactly once.
When greedy is the wrong tool
Use greedy when you can name the dominance rule: shorter reach is dominated by farther reach, later finish is dominated by earlier finish, a failed prefix cannot contain a valid start. If that sentence is fuzzy, slow down before coding.