Jump Game II
Asked at Google, Atlassian, Oracle, Salesforce
Problem
Given an integer array nums where nums[i] represents the maximum jump length from position i, reach the last index in the minimum number of jumps. You can assume you can always reach the last index.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Atlassian | Medium | View all Atlassian questions → |
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
BFS/greedy approach: treat each position as a level. From all positions reachable at the current jump, compute all positions reachable in one more jump. The first time you reach the last index is the minimum jumps.
Visual walkthrough for [2,3,1,1,4]:
Jump 0: start at index 0, maxReach = nums[0] = 2. Can reach indices 1, 2.
Jump 1: from indices 1-2, maxReach = max(1+3, 2+1) = 4. Can reach indices 3, 4.
Index 4 is the last index. Minimum jumps = 2.
Optimized greedy: track the farthest reachable index and the end of the current jump range. When you reach the end of the range, you must jump (increment jumps) and extend the range to the farthest reachable.
Why it works: at each jump, you consider all positions reachable from the current range. The farthest any of them can reach is the boundary of the next range. You only jump when forced (at the current range boundary).
Edge cases: single element (0 jumps), array starting at the last index (0 jumps), all ones (n-1 jumps).
Optimal Approach
Step 1: If nums has 1 or fewer elements, return 0.
Step 2: Initialize jumps = 0, currentEnd = 0, farthest = 0.
Step 3: For i from 0 to n-2:
- farthest = max(farthest, i + nums[i])
- If i == currentEnd:
- jumps += 1
- currentEnd = farthest
- If currentEnd >= n-1, break
Step 4: Return jumps.
The key insight: you only increment jumps when you reach the boundary of the current range. At that point, you extend the range to the farthest point reachable from any position in the current range.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Confusing Jump Game II (minimum jumps) with Jump Game (just reachable). The first requires counting jumps with greedy BFS, the second only checks if the last index is reachable.
Using BFS level-by-level without tracking the current range boundary. The optimized greedy approach only increments jumps when you reach currentEnd, not at every position.
Advancing mid (or the loop index) when swapping with high in a two-pointer variant. In this greedy approach there is no such swap, but candidates often mix it up with sort-colors logic.
Forgetting that the farthest reachable index must be updated at every position, not just when a jump occurs. If you only update farthest at the boundary, you miss better reach from later indices.
Not handling the edge case where nums[0] is already large enough to reach the end in one jump. The loop should break early when currentEnd >= n - 1.
Solution Code
def jump(nums):
if len(nums) <= 1:
return 0
jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
if current_end >= len(nums) - 1:
break
return jumpsFrequently Asked Questions
What is the Jump Game II problem?
Given an integer array nums where nums[i] represents the maximum jump length from position i, reach the last index in the minimum number of jumps. You can assume you can always reach the last index.
How do you solve Jump Game II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Jump Game II?
Jump Game II is asked at Google, Atlassian, Oracle, Salesforce. It is a medium difficulty problem.
What are common mistakes on Jump Game II?
- Confusing Jump Game II (minimum jumps) with Jump Game (just reachable). The first requires counting jumps with greedy BFS, the second only checks if the last index is reachable.
- Using BFS level-by-level without tracking the current range boundary. The optimized greedy approach only increments `jumps` when you reach `currentEnd`, not at every position.
- Advancing `mid` (or the loop index) when swapping with `high` in a two-pointer variant. In this greedy approach there is no such swap, but candidates often mix it up with `sort-colors` logic.
- Forgetting that the farthest reachable index must be updated at every position, not just when a jump occurs. If you only update `farthest` at the boundary, you miss better reach from later indices.
- Not handling the edge case where `nums[0]` is already large enough to reach the end in one jump. The loop should break early when `currentEnd >= n - 1`.