Search
⌘K
Get Premium
Greedy Algorithms
Jump Game II
medium
Count: 10
DESCRIPTION (credit Leetcode.com)
You are given an array of integers nums where each element represents the maximum jump length from that position. Your goal is to reach the last index starting from index 0. Write a function to return the minimum number of jumps needed to reach the last index. You can assume that you can always reach the last index.
Input:
nums = [2, 3, 1, 1, 4]
Output:
2
Explanation: Jump from index 0 to 1 (jump length 1), then jump from index 1 to 4 (jump length 3). Total = 2 jumps.
Input:
nums = [2, 3, 0, 1, 4]
Output:
2
Explanation: Jump from index 0 to 1, then jump from index 1 to 4. Even though index 2 has a 0, we skip over it.
Explanation
This is a follow-up to Jump Game. In that problem, we just needed to know if we could reach the end. Here, we need to find the minimum number of jumps to get there.
Understanding the Problem
Think of standing on platforms. Each platform has a number that tells you how far you can jump from there. You want to reach the last platform with as few jumps as possible.
For nums = [2, 3, 1, 1, 4]:
- From index 0 (value 2): Can jump to index 1 or 2
- From index 1 (value 3): Can jump to index 2, 3, or 4
- The optimal path: 0 → 1 → 4 (just 2 jumps!)
The Naive Approach: BFS
One way to think about this is like finding the shortest path in a graph. From each index, we can reach certain other indices. BFS would give us the minimum jumps.
But BFS requires a queue and potentially visiting the same index multiple times. Can we do better?
The Greedy Insight
Here's the key insight: we don't actually need to decide where to jump at each step. We just need to know when to count a jump.
Imagine you're at position 0 and can jump up to 2 steps. You don't need to decide right now whether to land on 1 or 2. What matters is:
- You'll need at least one jump to leave position 0
- After that jump, you'll be somewhere in the range [1, 2]
The clever part: while walking through this range, we keep track of the farthest position we could reach from anywhere in this range. That becomes our next boundary.
The Algorithm
We maintain three variables:
- jumps: Number of jumps made so far
- currentEnd: The farthest index reachable with the current number of jumps
- farthest: The farthest index reachable from any position we've seen so far
As we walk through the array:
- At each position, update farthest if we can reach further
- When we hit currentEnd (the boundary of our current jump), we must make another jump
- When we jump, currentEnd becomes farthest (the best we can do with one more jump)
Why This Works
This works because we're essentially doing BFS level by level, but without the queue overhead. Each "level" is defined by currentEnd - all positions reachable with the same number of jumps.
When we've processed all positions in the current level (reached currentEnd), we know the maximum reach from this level (farthest), and that becomes the boundary of the next level.
Walkthrough Example
Let's trace through nums = [2, 3, 1, 1, 4]:
Initial: jumps=0, currentEnd=0, farthest=0
i=0: Can reach 0+2=2. farthest=2. Hit boundary (i==currentEnd)! Jump #1, currentEnd=2
i=1: Can reach 1+3=4. farthest=4. Not at boundary yet.
i=2: Can reach 2+1=3. farthest still 4. Hit boundary (i==currentEnd)! Jump #2, currentEnd=4
We've reached the end (currentEnd >= n-1). Answer: 2 jumps
We only iterate up to nums.length - 1 because if we're at the last index, we don't need another jump. This also handles the edge case where currentEnd lands exactly on the last element.
Visualization
Visualization
Python
Finding the minimum jumps to reach the end
0 / 16
Solution
The solution walks through the array once, tracking how far we can reach and counting jumps only when we cross boundaries. This is essentially a level-order traversal disguised as a linear scan.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We iterate through the array exactly once, doing constant work at each step.
Space Complexity: O(1) We only use three variables regardless of input size.
Comparison with Jump Game I
| Aspect | Jump Game | Jump Game II |
|---|---|---|
| Question | Can we reach the end? | Minimum jumps to reach? |
| Tracking | Just maxReach | currentEnd + farthest |
| Return | Boolean | Integer (count) |
The core greedy insight is the same - we greedily track the maximum reach - but Jump Game II adds the boundary concept to count jumps.