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.

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

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

Reference:
http://www.programcreek.com/2014/03/leetcode-jump-game-java/

Analysis

We can track the maximum index that can be reached. The key to solve this problem is to find: 1) when the current position can not reach next position (return false) , and 2) when the maximum index can reach the end (return true).

The largest index that can be reached is: i + A[i].

Here is an example:

Java Solution

public boolean canJump(int[] A) {
    if(A.length <= 1)
        return true;

    int max = A[0]; //max stands for the largest index that can be reached.

    for(int i=0; i<A.length; i++){
        //if not enough to go to next
        if(max <= i && A[i] == 0) return false;
           //update max
        if(i + A[i] > max){
            max = i + A[i];
        }

        //max is enough to reach the end
        if(max >= A.length-1)
            return true;
    }

    return false;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s