Jump Game Cont..

Question: Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

You may view the full question here.

Approach 2: Let’s try tracing a path to the last index in the reverse order. Something like this —

Steps when there is A valid path

And what if there are no valid paths —

Steps when there are NO valid paths

Now let’s look at one last example —

Steps when there is A valid path, with a combination of successful and unsuccessful finds

And the code would look like —

//Approach 2:
//Runtime: 1ms
//Memory usage: 40MB
class Solution {
    public boolean canJump(int[] nums) {
        int dest = nums.length-1;
        int jump = 0;
        for(int i = nums.length - 2; i>=0;i--){
            if(i+nums[i]>=dest){
                if(i==0){
                    return true;
                } else {
                    dest=i;
                }
            }
        }
        return nums.length==1;
    }
}

Find more posts here.

Cheers & Chao!