# 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.

Example 1:

`Input: nums = [2,3,1,1,4]Output: 2Explanation: 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 `maxIndexReach`and `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.

--

--

--

## More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

## Jaydeep

Full Stack Programmer, love to solve problem’s during free time.