Jump Game

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.

class Solution {
    public boolean canJump(int[] nums) {
        int i, max = 0, length = nums.length;
        for(i=0;i<length && i<=max;i++){
            if(i+nums[i]>max){
                max = i+nums[i];
            }
        }
        return i == length;
    }
}

Try it on Leetcode

 Here, we are going to solve exactly what the question explains.

1) As problem statement indicates, we are storing max value and traversing each element of entire array.

2)  For each number, we are adding i with that index value and if it is greater than max then it has to be updated. [e.g., Initially i=0, max=0 from example1, max becomes 0+2 =2 which represents that i can reach maximum index of 2 from 0th position. Then for i=1, again repeat the same to find maximum index we can reach.]

3) For each i, if it is less than length and less than or equal to max then we can use that index value and apply step 2.

4) By repeating above steps if we can reach end of array, then it is true else it is false.

Please let us know your views in comment section.