Jump Game II
Greedy BFS-level jumps to the destination
Think of jump decisions as BFS levels: level 0 is your starting point, level 1 contains all indices reachable in 1 jump, level 2 all reachable in 2 jumps, and so on. Instead of maintaining an explicit queue, we track two frontiers: currEnd (the boundary of the current jump level) and farthest (the furthest index reachable from ANY cell in the current level). As we scan i, we update farthest = max(farthest, i + nums[i]). Whenever i reaches currEnd, we MUST spend a jump to enter the next level, setting currEnd = farthest. This finds the minimum jumps in one linear pass.
Details
Animated on: nums = [2, 3, 1, 1, 4] — find the minimum number of jumps needed to reach index 4.
Problem:Jump Game IIMedium
Pattern:Greedy Scheduling and Sorting
Greedy BFS-level jumps to the destination
step 1 / 8
Start at index 0 with jumps=0, currEnd=0, farthest=0. Destination is index 4.
- i=0· arr[0] = 2
- currEnd=0· arr[0] = 2
1FUNCTION jump(nums):2 jumps = 0, currEnd = 0, farthest = 03 FOR i from 0 to (length of nums) - 2:4 farthest = the larger of farthest and i + nums[i]5 IF i equals currEnd:6 add 1 to jumps7 currEnd = farthest8 RETURN jumps
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Start at index 0 with jumps=0, currEnd=0, farthest=0. Destination is index 4.
- i=0 (value 2): can reach up to index 0+2=2. Update farthest = 2.
- i reaches currEnd=0. We must take a jump: jumps becomes 1. Level 1 window is now [1..2] (currEnd = 2).
- i=1 (value 3): can reach index 1+3=4 (destination!). farthest extends to 4.
- i=2 (value 1): reach is 2+1=3 <= 4, so farthest remains 4.
- i reaches currEnd=2 (end of Level 1). Make Jump 2: jumps becomes 2, currEnd extends to 4.
- Loop finishes. currEnd=4 covers the final destination index 4.
- Minimum jumps to reach index 4 is 2 (path: index 0 → index 1 → index 4). Return 2.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.