Jump Game II

NeetCode: Jump Game II · LeetCode: 45. Jump Game II · Difficulty: Medium

The setup is the same as Jump Game, but the last index is guaranteed reachable. Return the minimum number of jumps needed to get from index 0 to the last index.

Example

Text

Input:  nums = [2, 4, 1, 1, 1, 1]    Output: 2    (0 -> 1 -> 5)
Input:  nums = [2, 1, 2, 1, 0]       Output: 2    (0 -> 2 -> 4)

Brute force: DP over indices

Let dp[i] be the fewest jumps to reach i. From each i, relax every index it can reach with dp[i] + 1. Unreached indices hold Integer.MAX_VALUE, and they are skipped so that dp[i] + 1 never overflows.

Java

import java.util.Arrays;

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == Integer.MAX_VALUE) {
                continue;
            }
            int last = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= last; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.jump(new int[]{2, 4, 1, 1, 1, 1}));
        System.out.println(s.jump(new int[]{2, 1, 2, 1, 0}));
        System.out.println(s.jump(new int[]{0}));
    }
}

Output

2
2
0

Time: O(n^2). Space: O(n).

Java

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int jumps = 0;
        int windowEnd = 0; // last index reachable with `jumps` jumps
        int far = 0;       // farthest index reachable with `jumps + 1` jumps
        for (int i = 0; i < n - 1; i++) {
            far = Math.max(far, i + nums[i]);
            if (i == windowEnd) {
                jumps++;
                windowEnd = far;
            }
        }
        return jumps;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.jump(new int[]{2, 4, 1, 1, 1, 1}));
        System.out.println(s.jump(new int[]{2, 1, 2, 1, 0}));
        System.out.println(s.jump(new int[]{0}));
    }
}

Output

2
2
0

Time: O(n). Space: O(1).

The loop stops before the last index (i < n - 1) because no jump starts there. For a single-element array the loop does not run and the answer is 0. i + nums[i] is an int sum and would wrap on overflow, which the problem's input limits avoid.