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

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution:

We maintains the max distance that we can jump (a greedy algorithm).

If at any position, we find we can jump to here, we set the max distance to be the max of previous max distance and the distance we can jump from the current position.

If we find we can jump to the end, return true.

After trying all positions, we know we have not reach the end, so we return false;

The time complexity is O(n).



Code:

public class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= maxReach) {
                maxReach = Math.max(maxReach, i + nums[i]);
            }
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}