LeetCode 55. Jump Game

Question

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

Source: https://leetcode.com/problems/jump-game/

Solution

The optimization idea is quite similar to finding Fibonacci number. For the current point, we only care about whether we can get to a point that can reach the end. Thus, we only need to maintain the index of left most point that can reach the end.

// DP, Time Complexity O(n^2)
public boolean canJump(int[] nums) {
    if (nums == null || nums.length == 0) {
        return false;
    }

    int len = nums.length;
    // dp[i] represents the quality of index i.
    // 1, -1, 0 means can reach the end, cannot reach the end and unknown respectively
    // in fact, a visited index with value of 0 can also be regarded as -1
    int[] dp = new int[len];
    dp[len - 1] = 1;
    for (int i = len - 2; i >= 0; i--) {
        int maxStep = nums[i];
        for (int k = 0; k <= maxStep && i + k < len; k++) {
            if (dp[i + k] == 1) {
                dp[i] = 1;
                break;
            }
        }
    }
    return dp[0] == 1;
}

// optimized DP, Time Complexity O(n)
public boolean canJump2(int[] nums) {
    if (nums == null || nums.length == 0) {
        return false;
    }
    int len = nums.length;
    // in the DP solution, we only use the left most index that can reach the end
    int leftMostGood = len - 1;
    for (int i = len - 2; i >= 0; i--) {
        if (i + nums[i] >= leftMostGood) { // i is a good index
            leftMostGood = i;
        }
    }
    // whether index 0 is a good index
    return leftMostGood == 0;
}