[LeetCode] Jump Game and Jump Game II (Java)

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.

Jump Game II

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.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Analysis

In Jump Game, we can save the farthest position we can reach when we go through the array. Every time we move, we will decrease the step. When we updating it, the step remaining for us is also updated. For example, for array A = [2, 3, 1, 1, 4], when we visit A[0], we update the maxReach to 2, and step to 2. When we visit A[1], we update maxReach to 1 + 3 = 4. And step is updated to 3. We will continue doing this until we reach the end or step getting to zero. If step getting to zero before we reach the end, it means that we can’t move forward so that we should return false.

In Jump Game II, we are asked for the minimum number of jumps. In fact, we only needs the number of jumps but not the path we jump. So that we can modify the code in Jump Game. We do not update step when we find a further position that we can reach. We only update it when step getting to 0. It means we can find the minimum number of jumps. In fact, in the test cases of this problem we can always reach the end. If we need to output -1 if we cannot reach the end, the code should be modified a little.

Code

Jump Game

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

public class Solution {

public boolean canJump(int[] A) {

if (A.length <= 1)

return true;

int maxReach = 0;

int step = 1;

for (int i = 0; i < A.length; i++) {

step--;

if (i + A[i] > maxReach) {

maxReach = i + A[i];

step = A[i];

}

if (step == 0 && i < A.length - 1)

return false;

}

return true;

}

Jump Game II

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
            if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            }
        }
        return jump;
    }
}

public class Solution {

public int jump(int[] A) {

if (A.length <= 1)

return 0;

int maxReach = A[0];

int step = A[0];

int jump = 1;

for (int i = 1; i < A.length; i++) {

if (i == A.length - 1)

return jump;

if (i + A[i] > maxReach)

maxReach = i + A[i];

step--;

if (step == 0) {

jump++;

step = maxReach - i;

}

return jump;

}

Complexity

We only go through the array once. So the complexity is only $O(n)$.