Jump Game

NeetCode: Jump Game · LeetCode: 55. Jump Game · Difficulty: Medium

You start at index 0 of nums, where nums[i] is the maximum jump length from index i. Return true if you can reach the last index.

Example

Text

Input:  nums = [1, 2, 0, 1, 0]    Output: true    (0 -> 1 -> 3 -> 4)
Input:  nums = [1, 2, 1, 0, 0]    Output: false   (every path gets stuck at index 3)

Brute force: reachability DP

Let reach[i] mean "index i can be reached". Index 0 is reachable; from every reachable index mark all indices it can jump to. Each index may mark up to n others.

Java

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] reach = new boolean[n];
        reach[0] = true;
        for (int i = 0; i < n; i++) {
            if (!reach[i]) {
                continue;
            }
            int last = Math.min(i + nums[i], n - 1);
            for (int j = i + 1; j <= last; j++) {
                reach[j] = true;
            }
        }
        return reach[n - 1];
    }
}

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

Output

true
false
true

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

Java

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

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

Output

true
false
true

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