Jump Game II
MediumCount the boundaries of each jump level
Problem
Given an array of max jump lengths, return the minimum number of jumps to reach the last index (assume it's always reachable).
Greedily jump to whatever spot lets you reach farthest next, counting one jump per 'frontier'.
The idea
Treat it as a BFS in levels: within the current jump's range, compute the furthest index reachable, and when you reach the end of the current range, increment the jump count and extend to that furthest point. Each level is one jump.
The trick
- Increment the jump count when i reaches the current range end.
- Do not step past the last index when checking the boundary, or you overcount by one.
- O(n), and it never needs to look backwards.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [2,3,1,1,4] Values: 2, 3, 1, 1, 4.
1jumps=0; curEnd=0; farthest=02for i in 0..n-2:3 farthest=max(farthest,i+nums[i])4 if i==curEnd: jumps++; curEnd=farthest5return jumpsInput
- array
- [2, 3, 1, 1, 4]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 3, 1, 1, 4]
- Output:
- 2
- Explanation:
- Hop 2 then 3 reaches the end in 2 jumps.
Example 2
- Input:
- nums = [2, 3, 0, 1, 4]
- Output:
- 2
- Explanation:
- Also 2 jumps.
Example 3
- Input:
- nums = [0]
- Output:
- 0
- Explanation:
- Already at the end → 0 jumps.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.