Greedy
On this page
A greedy algorithm builds the answer one step at a time and always takes the choice that looks best right now: the meeting that ends first, the farthest reachable index, the largest coin. It never revisits a choice. When it works, it is usually one pass after a sort: O(n) or O(n log n), with very little code.
The catch is that greedy is often wrong. Paying 6 with coins [1, 3, 4] by taking the largest coin first gives 4 + 1 + 1 (three coins), while 3 + 3 needs two. So with greedy, the interview is half code and half argument: why can't the local choice ever hurt?
When to recognise it
- "Maximum number of non-overlapping …", "minimum arrows / platforms / removals": sort by end time and take the earliest end.
- "Can you reach the end?", "minimum jumps": track the farthest reach.
- Partition a string or array so each piece satisfies a rule: extend the current piece as little as possible.
- Circular route with fuel (gas station), "assign cookies", "boats to save people": sort and match.
- A DP that only ever uses one choice: if every optimal solution can start with the same choice, a greedy rule exists.
Example 1: keep only the farthest reach
![Array [2, 3, 1, 1, 4] with indexes 0 to 4 and the farthest reach after each index: 2, 4, 4, 4, 8. By index 1 the reach is already 4, the last index, so the answer is True. For [3, 2, 1, 0, 4] the reac](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-25cecc8d.png)
You don't need to know which path reaches the end, only how far you can get. One number captures all paths tried so far.
def can_jump(nums):
"""Track the farthest index reachable so far; if we ever stand beyond it, we are stuck."""
farthest = 0
for i, step in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + step)
return True
The minimum number of jumps uses the same idea in layers: all indexes reachable with k jumps form a window, and the farthest point from that window is the edge of the next one. It is BFS without a queue.
def min_jumps(nums):
"""BFS by layers in disguise: each 'jump' covers the window reachable with one more jump."""
jumps = end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end: # used up the current jump's range
jumps += 1
end = farthest
return jumps
Example 2: earliest end first

def max_non_overlapping(intervals):
"""Interval scheduling: always keep the meeting that ENDS first. Exchange argument proves it."""
count, last_end = 0, float('-inf')
for s, e in sorted(intervals, key=lambda iv: iv[1]):
if s >= last_end:
count += 1
last_end = e
return count
Why it works (the exchange argument). Take any optimal answer. Its first meeting ends no earlier than the meeting greedy picked, so swap it for greedy's choice: nothing else in the answer overlaps the new one, and the count is the same. Repeat for the rest. Greedy is therefore never worse. Saying this in two sentences is what interviewers want to hear.
Example 3: extend to the last occurrence
def partition_labels(s):
"""Extend the current part to the last occurrence of every letter inside it."""
last = {ch: i for i, ch in enumerate(s)}
sizes, start, end = [], 0, 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
sizes.append(end - start + 1)
start = i + 1
return sizes
Each letter must stay inside one part, so the current part must stretch at least to the last occurrence of every letter in it. Cut as soon as you reach that point.
How to check a greedy idea
- State the rule in one sentence.
- Try to break it on small inputs: ties, equal values, one long item against many short ones.
- If you can't break it, give the exchange argument: any optimal answer can be changed to start with the greedy choice without getting worse.
- If you can break it, switch to DP 1D or DP 2D.
Common bugs
- Sorting by the wrong key: interval scheduling needs the end time. Sorting by start or length fails on some inputs.
- Assuming greedy works without checking: coin change is the standard trap.
>vs>=at boundaries: whether[1, 2]and[2, 3]overlap decides the comparison.- Jump game II loop bound: loop to
len(nums) − 1. Counting a jump when you are already on the last index adds one.
Say this in the interview
- "I'll always keep the meeting that ends earliest. Swapping it into any optimal schedule can't create an overlap, so greedy is optimal. Sorting dominates: O(n log n)."
- "Let me test the rule on a small counterexample before I commit to it."
Problems for this pattern
- Jump Game: farthest reach.
- Jump Game II: reach in layers.
- Gas Station: restart after the running fuel total goes negative.
- Partition Labels: extend to the last occurrence.
- Hand of Straights: always start a group at the smallest card left.
- Candy: one pass from each side.
Related
Intervals · DP 1D · Heaps and Top-K (many greedy choices are "take the best from a heap") · Pattern Recognition Cheat Sheet