You are given a 0-indexed array of integers nums
of length n
. You are initially positioned at nums[0]
.
Each element nums[i]
represents the maximum length of a forward jump from index i
. In other words, if you are at nums[i]
, you can jump to any nums[i + j]
where:
0 <= j <= nums[i]
andi + j < n
Return the minimum number of jumps to reach nums[n - 1]
. The test cases are generated such that you can reach nums[n - 1]
.
Example 1:
Input: nums = [2,3,1,1,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.
Example 2:
Input: nums = [2,3,0,1,4] Output: 2
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
nums[n - 1]
.This problem asks for the minimum number of jumps required to reach the last index of an array, where each element represents the maximum jump length from that index. A greedy approach provides an efficient solution.
The core idea is to iteratively find the farthest reachable index from the current position. We maintain three variables:
ans
: Counts the number of jumps made.mx
: Tracks the farthest index reachable from the current jump's starting point.last
: Keeps track of the last reached index after a jump.The algorithm iterates through the array (except for the last element). In each iteration:
Update mx
: Calculate the farthest reachable index from the current position (i + nums[i]
) and update mx
if this new reach is farther.
Check Jump Boundary: If the current index i
equals last
, it signifies that we've reached the boundary of the previous jump. This means we need to make another jump.
Update Jump Information: If a jump is needed:
ans
.last
to mx
to reflect the new reachable boundary.Finally, ans
will hold the minimum number of jumps required.
nums
array. We iterate through the array once.class Solution:
def jump(self, nums: List[int]) -> int:
ans = mx = last = 0
for i, x in enumerate(nums[:-1]): # Iterate up to second-to-last element
mx = max(mx, i + x) # Update farthest reachable index
if last == i: # Reached the boundary of the previous jump?
ans += 1 # Make a jump
last = mx # Update the boundary of the new jump
return ans
The code in other languages (Java, C++, Go, TypeScript, Rust, C#, C, PHP) follow the same logic, only differing in syntax and data structures. They all maintain the three variables (ans
, mx
, last
) and use the same iterative approach for finding the minimum jumps.
ans = 0
, mx = 0
, last = 0
.i = 0
, x = 2
: mx = max(0, 0 + 2) = 2
. last == i
(0 == 0), so ans = 1
, last = 2
.i = 1
, x = 3
: mx = max(2, 1 + 3) = 4
. last != i
(2 != 1).i = 2
, x = 1
: mx = max(4, 2 + 1) = 4
. last != i
(2 != 2).i = 3
, x = 1
: mx = max(4, 3 + 1) = 4
. last == i
(2 == 2), so ans = 2
, last = 4
.i
has reached the second-to-last element.ans = 2
.This shows that the minimum number of jumps needed is 2.