Jump Game II
Problem statement
You start at index 0 of an array nums. The value at each index tells you how far you're allowed to jump forward from there — from index i you can land on any index from i + 1 up to i + nums[i], as long as you don't go past the end of the array.
Find the smallest number of jumps needed to reach the last index. You're guaranteed that the last index is always reachable.
Examples
Example 1
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: Jump 1 step from index 0 to index 1, then 3 steps from index 1 straight to the last index — two jumps in total.
Example 2
Input: nums = [2, 3, 0, 1, 4]
Output: 2
Explanation: Index 2 holds a 0, which would be a dead end if you landed exactly there, but jumping from index 0 to index 1 and then to the last index still works in 2 jumps, skipping right over it.
Hints
Approach
Optimal: Greedy, range expansion
Intuition
You never actually need to decide, in advance, exactly which index to land on. Instead, track the furthest index reachable using every jump seen so far (farthest), and the furthest index the current jump is allowed to carry you to (currentEnd). As long as you're still inside the current jump's range, keep scanning and stretching farthest. The moment you reach the edge of what the current jump could reach, that means you must have taken another jump to get any further — so count it, and the new jump's reach becomes whatever farthest had grown to.
Steps
- Set
farthest = 0,currentEnd = 0, andjumps = 0. - Walk
ifrom 0 up to (but not including) the last index — you never need to jump from the last index. - At each
i, updatefarthest = max(farthest, i + nums[i]). - If
ihas reachedcurrentEnd(the range of the current jump is used up), incrementjumpsand setcurrentEnd = farthest. - Return
jumpsonce the loop finishes.
Dry run
nums = [2, 3, 1, 1, 4]
| i | farthest after update | i == currentEnd? | action | jumps after |
|---|---|---|---|---|
| 0 | max(0, 0+2) = 2 | yes (currentEnd starts at 0) | take jump, currentEnd = 2 | 1 |
| 1 | max(2, 1+3) = 4 | no (currentEnd = 2) | — | 1 |
| 2 | max(4, 2+1) = 4 | yes (currentEnd = 2) | take jump, currentEnd = 4 | 2 |
| 3 | max(4, 3+1) = 4 | no (currentEnd = 4) | — | 2 |
The loop stops before index 4 (the last index). Final answer: jumps = 2.
Edge cases: an array with one element never enters the loop (there's nothing before the last index to scan), so jumps stays 0.
Complexity
Time O(n) - one pass over the array; each index updates the farthest-reachable boundary exactly once.
Space O(1) - three counters, regardless of how long the array is.
class Solution:
def jump(self, nums):
n = len(nums)
jumps = 0
current_end = 0
farthest = 0
for i in range(n - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumps
if __name__ == "__main__":
print(Solution().jump([2, 3, 1, 1, 4]))
print(Solution().jump([2, 3, 0, 1, 4]))RecapThe whole problem in a few lines, for the night before
- Spot it: "fewest jumps to reach the end," where each position caps how far you can jump from it
- Idea: greedily expand the furthest index reachable within the current jump; take a new jump only once you've used up the current one's range
- Cost: O(n) time, O(1) space (greedy); O(n^2) time, O(n) space for the bottom-up DP; exponential for plain recursion
- Trap: stopping the loop at the last index instead of before it, which can count one extra, unneeded jump
Interview follow-ups
Return the actual sequence of indices used, not just the count of jumps.
Store, alongside
farthest, which index achieved that farthest reach at the moment you take each jump — that index is the one you "landed" on. Replaying those recorded indices after the loop finishes reconstructs one valid shortest path. This adds an O(n) array to remember the choices, but keeps the O(n) time.What if each index also has a cost associated with jumping from it, and you want the cheapest path among all shortest ones?
The pure greedy range-expansion trick stops being enough once jumps aren't all equal, because it only tracks reachability, not cost. This becomes a shortest-path problem on a graph where each index has an edge to everywhere it can reach — a 0-1 BFS or Dijkstra's algorithm over that graph finds the minimum-cost path in O(n log n) using a priority queue, since edge weights are non-negative.
Frequently asked questions
Because we're never committing to one specific landing index — we're expanding the set of indices reachable within the current jump count. Every index inside the current range gets looked at before we decide to take another jump, so farthest always reflects the true best possible reach for the next jump, not a guess. That means the jump count returned is provably the minimum, not just a good estimate.
Once you're standing on the last index, you're already done — there's nothing left to jump for. Including it in the loop would let farthest update past the array's bounds for no benefit, since the answer doesn't change once currentEnd already covers the last index.
It's a clean test of greedy reasoning under a constraint that looks like it needs backtracking at first glance — the same instinct used when planning the fewest hops through a chain of proxies, or the fewest batches needed to roll out a change across a set of hosts where each host can "reach" a limited number of others in one step.
Yes — a 0 only means you can't jump from that index. As long as some earlier index's range skips over it (the way index 1 skips over the 0 at index 2 in Example 2), the greedy tracking of farthest naturally routes around it without any special-case code.
