Jump Game II
Given an array of non-negative integers
nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.
Input: nums = [2,3,1,1,4]
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.
Input: nums = [2,3,0,1,4]
1 <= nums.length <= 104
0 <= nums[i] <= 1000
- Initialize the maximum position that one could reach and the maximum position reachable during the first hop as
maxIndexReach = numsand
currentIndexReach = numsrespectively.
- If the size of our array is greater than 1, then initialize the
- Start iterating over the array.
- In each iteration, update the
maxIndexReachso it contains the maximum position one could reach from the current index
ias max of
i + nums[i](addition of current position and from the current position maximum jump value).
- During iteration, if current array index position
i > currentIndexReach, it means that we are ready for another jump as we have already crossed the last max jump position. Increment
currentIndexReachto the current maximum position, which is
maxIndexReach. At this point if the
currentIndexReachis equal to our destination index which is the last index we can return the no of jumps as an answer.
- Return the number of jumps when the loop exits.
The time complexity will be O(n) because we iterate the array only once.
The space complexity will be O(1) because constant space is utilized.