Jump Game II
Problem
Given an array of non-negative integers nums, where each element represents the maximum jump length at that position, return the minimum number of jumps required to reach the last index of the array.
- 1 ≤ nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ 1000
- You can always reach the last index
Example
nums = [2,3,1,1,4]2Starting at index 0 with value 2, the algorithm considers all reachable indices within the current jump range [0,0]. It finds the farthest reachable index in this range is index 2 (0 + nums[0] = 2). Then it jumps to the next range [1,2]. Within this new range, it finds the farthest reachable index is 4 (1 + nums[1] = 4), which is the last index. Thus, it takes 2 jumps to reach the end.
Approach
Straightforward Solution
A brute-force approach tries all possible jump sequences, exploring every reachable index recursively or via BFS, resulting in exponential or O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
At any point, the minimum number of jumps corresponds to the number of times the reachable range must be extended to cover the last index. The problem reduces to tracking the current range of indices reachable with the current number of jumps and greedily expanding to the farthest reachable index in the next jump.
Path to Optimal
The key recognition signals are 'minimum number of jumps' and 'maximum jump length at each position'. These indicate a Greedy approach because the problem can be viewed as expanding reachable ranges layer by layer, where each jump extends the coverage as far as possible. Instead of exploring all paths, the algorithm tracks the current jump's coverage and the farthest reachable index for the next jump, incrementing the jump count only when the current coverage is exhausted.
Optimal Approach
Use two pointers to represent the current jump's coverage (l and r). For each jump, iterate over the indices in the current coverage to find the farthest reachable index (farthest). Then update the coverage to [r+1, farthest] and increment the jump count. Repeat until the coverage reaches or passes the last index. This greedy expansion guarantees the minimum number of jumps in O(n) time.
Time
O(n)
Each index is visited at most once in the inner loop as the coverage range moves forward, resulting in a linear scan of the array.
Space
O(1)
Only a fixed number of variables are used to track indices and counts, with no additional data structures proportional to input size.
Pattern Spotlight
Greedy Algorithms (Range Expansion)
When minimizing the number of jumps or steps over a sequence with variable reach, track the current coverage range and greedily extend it to the farthest reachable index before incrementing the jump count, ensuring each jump covers the maximum possible distance.
Solution
| 1 | class Solution:
|
| 2 | def jump(self, nums: list[int]) -> int:
|
| 3 | res = 0
|
| 4 | l = r = 0
|
| 5 |
|
| 6 | while r < len(nums) - 1:
|
| 7 | farthest = 0
|
| 8 | for i in range(l, r + 1):
|
| 9 | farthest = max(farthest, i + nums[i])
|
| 10 |
|
| 11 | l = r + 1
|
| 12 | r = farthest
|
| 13 | res += 1
|
| 14 |
|
| 15 | return res |
Step-by-Step Solution
Initialize Jump Count and Coverage Pointers
| 3 | res = 0
|
| 4 | l = r = 0
|
Objective
To set up the initial state variables for counting jumps and tracking the current coverage range.
Key Insight
Starting with zero jumps and coverage pointers at the first index reflects that no jumps have been made yet and the initial coverage is just the starting position. This setup is essential for the greedy expansion logic to correctly track reachable indices and increment jumps only when coverage is extended.
Interview Quick-Check
Core Logic
Initializing both left and right pointers to zero sets the initial coverage range to the first index, representing the starting point before any jumps.
State & Boundaries
The jump count starts at zero because no jumps have been made at the start.
Expand Coverage Range Greedily Until Last Index is Reachable
| 6 | while r < len(nums) - 1:
|
| 7 | farthest = 0
|
| 8 | for i in range(l, r + 1):
|
| 9 | farthest = max(farthest, i + nums[i])
|
| 11 | l = r + 1
|
| 12 | r = farthest
|
| 13 | res += 1
|
Objective
To iteratively find the farthest reachable index within the current coverage and update the coverage range while counting jumps.
Key Insight
By scanning all indices within the current coverage range and calculating the farthest reachable index from these positions, the algorithm ensures that each jump covers the maximum possible distance. Updating the coverage pointers to the next range and incrementing the jump count only after exhausting the current coverage guarantees minimal jumps. This approach avoids exploring all paths and achieves linear time complexity.
Interview Quick-Check
Core Logic
The inner loop finds the farthest reachable index from the current coverage, and the outer loop updates coverage and increments jumps until the last index is reachable.
State & Boundaries
The while loop condition ensures the process continues until the coverage includes the last index.
Common Pitfalls & Bugs
Failing to update the coverage pointers correctly or incrementing the jump count too early can lead to incorrect jump counts or infinite loops.
Complexity
The nested loop structure still results in O(n) time because each index is visited at most once as coverage moves forward.
Return the Minimum Number of Jumps
| 15 | return res |
Objective
To output the total count of jumps required to reach the last index after coverage expansion completes.
Key Insight
Returning the jump count after the coverage range includes the last index provides the minimal number of jumps needed. This final step concludes the greedy process and delivers the solution.
Interview Quick-Check
Core Logic
Returning the jump count after the loop ensures the result reflects the minimal jumps needed to cover the entire array.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
farthest = max(farthest, i + nums[i])Update the farthest reachable index based on the current position and its jump length.
Calculating max(farthest, i + nums[i]) finds the maximum extent reachable from the current coverage, which is critical for greedy range expansion and minimizing jumps.
r = farthestUpdate the right pointer to the farthest reachable index found.
Setting r to farthest extends the coverage to the maximum reachable index from the previous range, enabling the greedy jump that covers the largest possible distance.
res += 1Increment the jump count after expanding the coverage range.
Incrementing res here reflects that a jump has been made to extend coverage, and doing so only after fully exploring the current range ensures minimal jumps are counted.
l = r = 0Initialize left and right pointers to zero to represent the current coverage range.
Setting both pointers to zero defines the initial coverage as the starting index, which is essential for the greedy range expansion logic to function correctly.
for i in range(l, r + 1):Iterate over all indices in the current coverage range [l, r].
Scanning all indices in the current coverage ensures the algorithm considers every possible jump from the current range, enabling the greedy selection of the farthest reachable index.
l = r + 1Move the left pointer to one position beyond the current right pointer to start the next coverage range.
Updating l to r + 1 shifts the coverage window forward, marking the start of the next jump's range and ensuring no indices are revisited unnecessarily.
return resReturn the total number of jumps required to reach the last index.
Returning res after the coverage includes the last index provides the minimal jump count as computed by the greedy expansion process.
while r < len(nums) - 1:Continue looping while the right pointer is less than the last index.
This loop condition ensures the algorithm continues expanding coverage until the last index is reachable, which is the termination condition for the minimal jumps calculation.
farthest = 0Initialize the farthest reachable index for the next jump to zero.
Resetting the farthest variable at each iteration allows the algorithm to find the maximum reachable index from the current coverage range, which guides the next coverage update.
res = 0Initialize the jump count to zero.
Starting with zero jumps reflects that no moves have been made yet, establishing the baseline for counting jumps as the algorithm progresses.
Test Your Understanding
Why does incrementing the jump count only when the current coverage range is exhausted guarantee the minimum number of jumps?
Because each jump covers the maximum possible range reachable from the current coverage, delaying the jump count increment until no further indices in the current range can extend coverage ensures that jumps are only made when necessary, minimizing their total number.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Jump Game II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Jump Game II drill