Leetcode — 55. Jump Game

The link to the problem: https://leetcode.com/problems/jump-game/

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index of the array.

Constraints:

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

For example, when nums = [2,3,1,1,4], output = true. There are multiple ways we can reach the last index, one way is jump from index 0 -> index 1 -> index 4.

⚠️ There will be three codes in this article, you can see how my code improved from running 252 ms -> 2 ms -> 1ms.

Thoughts:

My first thought is to use dynamic programming to solve the problem. We can have an integer array named dp to store the longest position that the current position can reach. i.e., dp[i] represents the furthest position we can reach from position i.
The initial value of all the values in dp array is -1, which represents we will never reach that point. ⛔️

The code looks like below:

public boolean canJump(int[] nums) {
        int n = nums.length;
        //dp[i] stores the farest we can jump from pos i
        int[] dp = new int[n]; 
        //n-1 is our target
        Arrays.fill(dp,-1);
        dp[0] = 0; //starting point
        for(int i=0;i<n;i++)
        {
            if(dp[i]==-1) //will never reach this point
                return false;
            dp[i] = i + nums[i];
            if(dp[i]>=n-1)
                return true;
            for(int j=i+1;j<=dp[i];j++)
                dp[j] = 0;
        }
        return false;
    }

The reason why the above code only beats 28% is because of the high time complexity. It will run O(n²) since after assigning the value for dp[i], we need to update the values of all the reachable positions.

Here comes the question, how do we improve our 252 ms code? Is there any way that we can only run O(n)?

In the previous code, we keep updating the reachable values to keep track of whether we can reach that point.
Instead of using -1 to determine if we reach the point, what we can do is use an additional variable to represent the furthest position we can reach.

public boolean canJump(int[] nums) {
        int n = nums.length;
        //dp[i] stores the farest we can jump from pos i
        int[] dp = new int[n]; 
        //n-1 is our target
        int reachable = 0;
        for(int i=0;i<n;i++)
        {
            if(reachable<i)
                return false;
            dp[i] = i + nums[i];
            reachable = Math.max(dp[i],reachable);
            if(reachable>=n-1)
                return true;
        }
        return false;
    }

After adding these highlighted lines in the code, now the code runs 2ms which beats 41%. Time complexity and space complexity are both O(n).

Then, you can also do a little modification to the above code. You might notice that we actually didn’t really need the dp array since we already use the extra variable to control the furthest position we can reach.

public boolean canJump(int[] nums) {
        int n = nums.length;
        //n-1 is our target
        int reachable = 0;
        for(int i=0;i<n;i++)
        {
            if(reachable<i)
                return false;
            reachable = Math.max(i+nums[i],reachable);
            if(reachable>=n-1)
                return true;
        }
        return false;
    }

The above code now runs 1ms which beats 85%.

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