Jump Game II
On this page
Problem statement
You start at index 0 of an array of non-negative integers. The value at each index is the longest jump you may make from there (you can also jump shorter). Return the minimum number of jumps needed to reach the last index. The input guarantees the last index is reachable.
The follow-up to Jump Game: there the question was "can you reach the end?", here it's "how fast?". It is a shortest path in disguise, and the trick is to run a BFS without building a graph. Original problem: LeetCode 45.
Example

Input: [2, 4, 1, 1, 3, 1, 1]
Output: 3 # 0 -> 1 -> 4 -> 6 (or 0 -> 1 -> 5 -> 6)
Input: [1, 1, 1]
Output: 2
Input: [0]
Output: 0 # already at the last index
Constraints (assumed)
- 1 ≤ n ≤ 10⁴; 0 ≤ nums[i] ≤ 1,000.
- The last index is always reachable.
What this question tests
- Seeing the problem as a shortest path where every edge costs one jump.
- Replacing an explicit BFS with windows of indices ("everything reachable in j jumps").
- Not being fooled by the tempting greedy "always jump as far as possible".
Questions to ask first
- Is the end always reachable? (Here: yes. Otherwise return −1, and the code must detect a stuck window.)
- Can I jump shorter than the value? (Here: yes, any length from 1 to nums[i].)
- Do you need the path or just the count? (Here: the count.)
- How large is n? O(n²) DP is fine for small n, not for 10⁴ with big values.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.