Jump Game II

Source

LeetCode 45 Jump Game II

LintCode 116 Jump Game II

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.

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

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

Solution

The first solution is DP solution. While we iterate through the original array, fill the dp array for where it can be reached within next step and increment maximum reachable index.

public int jump(int[] A) {
    if (A.length <= 1) {
        return 0;
    }

    int[] steps = new int[A.length];

    int reachable = 0;
    for (int i = 0; i < A.length; i++) {
        //if (i != 0 && steps[i] == 0) return 0;
        if (i + A[i] >= A.length - 1) return steps[i] + 1;

        int maxIndex = i + A[i];
        while (reachable + 1 <= maxIndex) {
            steps[reachable+1] = steps[i] + 1;
            reachable++;
        }
    }

    return 0;
}

The second solution is a non-DP one. It uses two indices to mark out the range numbers that can be reached within same steps. For each iteration in these ranges, it increments the max reachable index for the next step, and at the end of the iteration, the max reachable will become the new right index.

public int jump(int[] nums) {
    if (nums == null || nums.length <= 1) return 0;
    int left = 0;
    int right = 0;
    int steps = 0;

    while (left <= right) {
        steps++;
        int reachable = right;
        for (int i = left; i <= right; i++) {
            reachable = Math.max(reachable, i + nums[i]);
        }

        if (reachable >= nums.length - 1) return steps;


        left = right + 1;
        right = reachable;
    }
    return 0;

}