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

Solution:

You probably would have seen the solution many times. I’ll try to explain it in a better way. You’ll be the judge if I have succeeded or not. Lets start.

Taking nums, we start from index 0 and we get 2. So we know we can move two steps from 0th index. And we also know that curr_index + nums[curr_index], that is 0 + 2 will be the maximum index we can reach from 0. Steps taken to reach 2nd index from 0th index will be 1, that is steps to reach 0th index + 1. We also know that minimum steps to reach 1st index and 2nd index will also be 1 no matter what value we get between 0th index and 2nd index.

Now lets move forward. Now we are at 1st index and value is 3. So maximum index we can reach from 1st index is curr_index + nums[curr_index] that is 1 + 3 will be the maximum index we can reach from 1. Steps taken to reach 4th index will be 2, that is steps to reach 1st index + 1. So, again we know that minimum number of steps to reach 4th index will be 2 no matter what value we get in between 1st and 4th index.

Since we got to last index we can return but for explanation, lets keep on going for one more index.

Next we’ll be at 2nd index and value is 1. So maximum index we can reach from here is 2+1 = 3rd index. Since this maximum index is less than 4th index, we wont update steps or do anything else as we know this is not the minimum steps to reach 3rd index.

Let see the code now.

def jump(self nums):
        currEnd, currFarthest, jumps = 0, 0, 0
        for i in range(len(nums)-1):
            currFarthest = max(currFarthest, i+nums[i])
            if i == currEnd:
                currEnd = currFarthest
                jumps += 1
        return jumps

I wrote it in a bit of haste. Please post questions in the comments. Thanks.