Jump Game II
Medium· Greedy Reach· Implicit BFS
Problem
Same jumping rules as Jump Game, and the last index is guaranteed to be reachable. Return the minimum number of jumps needed to get there from index 0.
Examples
Input: nums = [2,3,1,1,4]
Output: 2
Index 0 -> index 1 -> last index.
Input: nums = [2,3,0,1,4]
Output: 2
Constraints
- • 1 <= nums.length <= 10^4
- • 0 <= nums[i] <= 1000
- • The last index is reachable
Hints & approach
Hint 1
Think of it as BFS where each "level" is the range of indices reachable with k jumps.
Hint 2
While scanning the current range, compute the furthest point the next range can extend to.
Hint 3
When you reach the end of the current range, you must spend one more jump.
Approachtry the hints first
Keep jumps, the end of the current range, and the furthest reach found so far. For every index before the last, update furthest = max(furthest, i + nums[i]). When i reaches the current end, increment jumps and set end = furthest, which opens the next level. This is BFS over ranges without a queue.
Time O(n) · Space O(1)