Jump Game II
Minimum jumps to reach the last index — BFS-style "current reach" frontier.
3 min read
greedy array
Problem#
Same as Jump Game I but return the minimum number of jumps to reach the last index. Reachability is guaranteed.
Examples#
[2,3,1,1,4]→2[2,3,0,1,4]→2
Constraints#
1 <= n <= 10^4.
Approach#
Implicit BFS: maintain currentEnd (end of “this jump”) and farthest (max reach from anywhere in the current segment). When you reach currentEnd, commit a jump and set currentEnd = farthest.
Solution#
class Solution {public: int jump(vector<int>& nums) { int jumps = 0, currentEnd = 0, farthest = 0; for (int i = 0; i < (int)nums.size() - 1; ++i) { farthest = max(farthest, i + nums[i]); if (i == currentEnd) { ++jumps; currentEnd = farthest; } } return jumps; }};func jump(nums []int) int { jumps, currentEnd, farthest := 0, 0, 0 for i := 0; i < len(nums)-1; i++ { if i+nums[i] > farthest { farthest = i + nums[i] } if i == currentEnd { jumps++ currentEnd = farthest } } return jumps}from typing import List
class Solution: def jump(self, nums: List[int]) -> int: jumps = current_end = farthest = 0 for i in range(len(nums) - 1): if i + nums[i] > farthest: farthest = i + nums[i] if i == current_end: jumps += 1 current_end = farthest return jumpsfunction jump(nums) { let jumps = 0, currentEnd = 0, farthest = 0; for (let i = 0; i < nums.length - 1; i++) { if (i + nums[i] > farthest) farthest = i + nums[i]; if (i === currentEnd) { jumps++; currentEnd = farthest; } } return jumps;}class Solution { public int jump(int[] nums) { int jumps = 0, currentEnd = 0, farthest = 0; for (int i = 0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i == currentEnd) { jumps++; currentEnd = farthest; } } return jumps; }}function jump(nums: number[]): number { let jumps = 0, currentEnd = 0, farthest = 0; for (let i = 0; i < nums.length - 1; i++) { if (i + nums[i] > farthest) farthest = i + nums[i]; if (i === currentEnd) { jumps++; currentEnd = farthest; } } return jumps;}Editorial#
Conceptually a BFS over “how many jumps to reach index i?”. The trick is that within a “jump level” (positions reachable in j jumps), we know the next level’s frontier without explicitly enqueueing — it’s just the max-reach across the current level. Loop ends at n - 2 because reaching the last index doesn’t require an additional outgoing jump.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#