Jump Game II

Photo by Nicolas Picard on Unsplash

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.

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

Solution

1. Initialize the maximum position that one could reach and the maximum position reachable during the first hop as maxIndexReach = nums[0] and currentIndexReach = nums[0] respectively.
2. If the size of our array is greater than 1, then initialize the maxJumps variable to 1.
3. Start iterating over the array.
4. In each iteration, update the maxIndexReach so it contains the maximum position one could reach from the current index i as max of maxIndexReachand i + nums[i](addition of current position and from the current position maximum jump value).
5. 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 maxJumps by 1 and assign currentIndexReach to the current maximum position, which is maxIndexReach. At this point if the currentIndexReach is equal to our destination index which is the last index we can return the no of jumps as an answer.
6. Return the number of jumps when the loop exits.

Time complexity

The time complexity will be O(n) because we iterate the array only once.

Space complexity

The space complexity will be O(1) because constant space is utilized.