Jump Game

Source

LintCode 116 Jump Game

Problem

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

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

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

Solution

There are two solutions, the first solution is using an extra boolean array to keep track of which position can be reached. When we iterate through the array, we flag up those reachable positions.

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

    boolean[] canReach = new boolean[A.length];
    canReach[0] = true;
    for (int i = 0; i < A.length; i++) {
        if (!canReach[i]) return false;
        int maxIndex = Math.min(i + A[i], A.length - 1);
        for (int j = i+1; j <= maxIndex; j++) {
            canReach[j] = true;
        }
    }
    return canReach[A.length - 1];
}

The second solution, also a better solution, is to only keep a maximum index that can be reached so far. And as we iterate through the array, we keep updating the maximum index until it hits the last position (return true), or the current index exceeds the maximum index (return false).

public boolean canJump(int[] A) {
    if (A == null || A.length == 0) return false;

    int index = 0, maxReach = 0;
    int lengthToWin = A.length - 1;
    while (index <= maxReach) {
        if (index + A[index] >= lengthToWin) {
            return true;
        }
        maxReach = Math.max(maxReach, index + A[index]);
        index++;
    }
    return false;
}