#45
Jump Game II
Medium BFS by ranges
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Same jumps as Jump Game, and the end is always reachable. Return the minimum number of jumps to reach the last index.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the fewest jumps to the end.
Why this works: think in levels: all indexes reachable in j jumps form a range; the next range ends at the furthest point reachable from it.
Example: [2, 3, 1, 1, 4]
jump 1 covers indexes 1..2from there furthest 4 → jump 2 → done
✦Hints open one at a time
Think of levels: all indexes reachable with j jumps form a range.
The next range ends at the furthest point reachable from the current range.
↗Approach
Keep the end of the current range and the furthest reach. When i hits the current end, you must jump: count it and set the end to the furthest reach.
</>Solution (Java)
class Solution {
public int jump(int[] nums) {
int jumps = 0, curEnd = 0, furthest = 0;
for (int i = 0; i < nums.length - 1; i++) { // no jump needed from the last index
furthest = Math.max(furthest, i + nums[i]);
if (i == curEnd) { // range used up: jump
jumps++;
curEnd = furthest;
}
}
return jumps;
}
}!Common mistake
Looping up to the last index inclusive and counting an extra jump when you're already there.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Greedy
🎬 Episodes 69–73: video coming soon