You are given an array of integers nums, where nums[i] represents the maximum length of a jump towards the right from index i. For example, if you are at nums[i], you can jump to any index i + j where:
j <= nums[i]i + j < nums.lengthYou are initially positioned at nums[0].
Return the minimum number of jumps to reach the last position in the array (index nums.length - 1). You may assume there is always a valid answer.
Example 1:
Input: nums = [2,4,1,1,1,1]
Output: 2
Explanation: Jump from index 0 to index 1, then jump from index 1 to the last index.
Example 2:
Input: nums = [2,1,2,1,0]
Output: 2
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 100
You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.
A brute force approach would be to recursively explore all paths from index 0 to its reachable indices, then process those indices similarly and return the minimum steps to reach the last index. This would be an exponential approach. Can you think of a better way? Maybe a greedy approach works.
We maintain two pointers, l and r, initially set to 0, representing the range of reachable indices. At each step, we iterate through the indices in the range l to r and determine the farthest index that can be reached from the current range.
We then update the pointers l and r to the next range, setting l to r + 1 and r to the farthest index reachable from the current range. We continue this process until the pointers go out of bounds.
The number of steps taken represents the minimum steps required to reach the last index, as it is guaranteed that we can reach it.
{
"nums": [
1
]
}0{
"nums": [
2,
1
]
}1{
"nums": [
2,
3,
1,
1,
4
]
}2Sign in to Run Code and Submit