Greedy, and how to defend it
Make the locally best choice when you can prove an exchange argument shows it never hurts.
Jump Game II. nums[i] is the maximum jump length from index i. Starting at index 0, return the minimum number of jumps to reach the last index (it is always reachable).
Signals that point here
- Scheduling and intervals: fewest removals for no overlaps, minimum arrows, meeting rooms.
- "Minimum number of steps" where each step's reach can be summarised by one number.
- Problems where sorting by one key makes the next choice obvious.
The idea
This is BFS in disguise: all indices reachable in j jumps form a contiguous range, so you only need the range's end and the farthest point reachable from inside it. When i hits the end of the current layer, take a jump and the next layer's end becomes far.
A greedy answer needs a defence. The standard one is an exchange argument: take any optimal solution, swap its first choice for the greedy choice, and show it is no worse. If you cannot sketch that in two sentences, propose DP instead and say why.
def min_jumps(nums: list[int]) -> int:
jumps = layer_end = farthest = 0
for i in range(len(nums) - 1): # never jump FROM the last index
farthest = max(farthest, i + nums[i])
if i == layer_end: # finished this layer: take a jump
jumps += 1
layer_end = farthest
return jumpspublic static class Greedy
{
public static int MinJumps(int[] nums)
{
int jumps = 0, layerEnd = 0, farthest = 0;
for (int i = 0; i < nums.Length - 1; i++) // never jump FROM the last index
{
farthest = Math.Max(farthest, i + nums[i]);
if (i == layerEnd) // finished this layer: take a jump
{
jumps++;
layerEnd = farthest;
}
}
return jumps;
}
}Complexity
O(n) time, O(1) space.
Pitfalls interviewers watch for
- Looping to the last index, which adds a spurious jump when
i == layer_endthere. - Jumping to the cell with the largest value (a different, wrong greedy).
- Asserting greedy works without an argument; interviewers will ask for one.
Variants worth knowing
- Jump Game I (can you reach the end?): track
farthestand fail ifi > farthest. - Non-overlapping intervals: sort by end, keep each interval that starts after the last kept end.
- Gas station: if total gas >= total cost, the start is just after the point where the running tank went most negative.
Test it like the interviewer will
min_jumps([2, 3, 1, 1, 4])returns2min_jumps([2, 3, 0, 1, 4])returns2min_jumps([0])returns0min_jumps([1, 1, 1, 1])returns3- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: min_jumps([2, 3, 1, 1, 2, 1, 4])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the minimum number of intervals to remove so the rest do not overlap.
- Find the starting gas station that lets you complete the circuit, or -1.
- Partition a string into as many parts as possible so each letter appears in at most one part.
Check yourself
What argument usually proves a greedy algorithm correct?
An exchange argument: replacing an optimal solution's choice with the greedy one does not make it worse.
Why loop only to len(nums) - 1?
You never need to jump from the last index; including it can add one jump too many.