Coding Interview PatternsJump Game II
MediumGreedy Techniques
Jump Game II
Explanation & Solution
Description
Given a 0-indexed array of integers nums where each element represents the maximum length of a forward jump from that index, return the minimum number of jumps to reach the last index.
You can assume that you can always reach the last index.
Input:nums = [2,3,1,1,4]
0
2
1
3
2
1
3
1
4
4
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Constraints
1 <= nums.length <= 10^40 <= nums[i] <= 1000- It is guaranteed that you can reach
nums[n - 1]
Approach
Greedy Techniques pattern
1. Initialize Tracking Variables
jumps = 0counts the minimum number of jumps taken so farcurrentEnd = 0marks the farthest index reachable with the current number of jumpsfarthest = 0tracks the farthest index reachable from any position within the current jump range
2. Iterate Through the Array
- Loop from index
0tonums.length - 2(we stop before the last index because we don't need to jump from it) - At each index
i, updatefarthest = Math.max(farthest, i + nums[i])to track the maximum reach
3. Decide When to Jump
- When
i === currentEnd, we have explored every index reachable with the current number of jumps - At this point, we must take another jump, so increment
jumps - Set
currentEnd = farthestto extend our reachable range to the farthest point discovered
4. Return the Result
- After the loop completes,
jumpsholds the minimum number of jumps needed to reach or pass the last index
Key Insight
- This is a greedy BFS approach: each "level" of the BFS represents all indices reachable with a given number of jumps
currentEndacts as the boundary of the current BFS level, andfarthestacts as the boundary of the next level- By greedily extending to the farthest reachable index at each level, we guarantee the minimum number of jumps
Visualization
Input:
[2, 3, 1, 1, 4]
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
6 steps