Jump Game II
Problem Statement
You are given a zero-indexed integer array nums of length n. You start at index 0, and nums[i] is the maximum jump length from index i. Return the minimum number of jumps needed to reach index n - 1. The input is guaranteed to be reachable.
Input
An integer array nums, where each value is the maximum jump length from that index.
Output
An integer: the minimum number of jumps required to reach the last index.
Constraints
- •
1 <= nums.length <= 10^4 - •
0 <= nums[i] <= 1000 - •
It is guaranteed that the last index is reachable
Examples
Example 1
nums = [2,3,1,1,4]
2Example 2
nums = [2,3,0,1,4]
2Learning Objectives
- View greedy jump counting as BFS-like level expansion over index ranges.
- Track the farthest next boundary reachable within the current jump.
- Increment the jump count only when the current level has been fully scanned.
- Avoid O(n^2) exploration of every edge in the implicit jump graph.
Intuition
Greedy Insight: treat all indices reachable with the current number of jumps as one BFS-like level. While scanning that level, compute the farthest index any of those positions can reach with one more jump. When the scan reaches the end of the current level, you must spend one jump, and the next level ends at that farthest boundary.
The tempting wrong idea is to jump immediately to the index with the largest number written on it. The right comparison is not the local value nums[i], but the resulting reach i + nums[i] among all positions in the current level. That is exactly what BFS would do if it expanded all edges, but the range representation makes it O(n).
Common mistakes
- ×Incrementing jumps at every index instead of only at the end of the current range.
- ×Choosing the next index by largest **nums[i]** rather than largest **i + nums[i]**.
- ×Looping through the last index and adding an unnecessary extra jump.
- ×Using O(n^2) BFS over every possible jump edge even though ranges can be collapsed.
Algorithm Explanation
Greedy strategy
Maintain two boundaries: currentEnd, the farthest index reachable with the current number of jumps, and farthest, the farthest index reachable with one additional jump from any index scanned in the current range. When the scan reaches currentEnd, commit one jump and move currentEnd to farthest.
Why it works
All indices inside the current range are reachable with the same number of jumps. Since one more jump may start from any of them, the best next range is determined by the maximum i + nums[i] over the whole current range. Committing earlier would ignore a possible better launch point in the same level.
Proof of correctness
Consider the first jump count where an optimal solution chooses a next boundary smaller than the greedy farthest after scanning the current level. The greedy boundary is produced by some index reachable with the same number of jumps as every other index in that level. Replacing the optimal next boundary with the greedy boundary uses the same number of jumps and reaches at least as far, so it cannot make any future completion worse. By this exchange, there is an optimal solution whose boundary choices match the greedy choices at every level. Therefore the number of times we close a level is the minimum number of jumps.
Algorithm
- If the array has one element, return 0.
- Set jumps = 0, currentEnd = 0, and farthest = 0.
- Scan indices from 0 through n - 2.
- Update farthest with max(farthest, i + nums[i]).
- When i == currentEnd, increment jumps and set currentEnd = farthest.
- Once currentEnd reaches the last index, return jumps.
Solutions
Solution: BFS-level greedy range expansion
Collapse the implicit BFS graph into contiguous ranges. The current range contains all indices reachable with the current number of jumps; scanning it computes the next range boundary in one pass.
Step-by-step
- Start with zero jumps, currentEnd = 0, and farthest = 0.
- Scan every index before the last index, because reaching the last index ends the problem.
- For each index, update farthest using index + nums[index].
- When the scan index reaches currentEnd, one BFS level is complete, so increment jumps and promote farthest to the new currentEnd.
- Return as soon as currentEnd covers the last index.
O(n)
O(1)
Each index enters exactly one range scan and only two boundaries are stored.
Java implementation
Dry Run
Sample input
nums = [2,3,1,1,4]. Treat indices reachable with the same jump count as a range.
| index | nums[index] | current jump end | farthest after scan | action |
|---|---|---|---|---|
| 0 | 2 | 0 | 2 | close level, jumps = 1, next end = 2 |
| 1 | 3 | 2 | 4 | scan inside current level |
| 2 | 1 | 2 | 4 | close level, jumps = 2, next end = 4 |
After closing the second level, currentEnd reaches index 4, so the minimum number of jumps is 2.
Interview Tips
Describe it as BFS without a queue. The queue would contain many indices, but because reachable indices form a contiguous range, currentEnd is enough to know when one jump layer ends. Also mention why the loop stops before the last index: you do not need to jump from the destination.
Likely follow-ups
- How would you return the actual indices chosen by the minimum-jump path?
- How would the algorithm change if the last index were not guaranteed reachable?
- Can you solve it with an explicit BFS, and why is that less efficient?
- What if each jump had a different cost rather than cost 1?
Similar Problems
Key Takeaways
- Minimum jumps are BFS layers over contiguous reachable ranges.
- Scan the whole current range before committing the next jump.
- The best next range is the maximum **i + nums[i]** inside the current range.
- Do not count a jump from the last index.