Blind 75.26 - Jump Game

Jump game.

Problem description

Taken directly from LeetCode.

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

Solution type

Caching via DP.

Solution

What might come as the obvious solution is to do a nested for loop with a memo, where the outer for loop iterates over all elements of nums and the inner for loop marks all memo[i + j] true, where i is the index of the current element of nums and j := 1..nums[i]. However, this is \(O(nj)\) where \(j\) is the maximum jump distance. We can make it \(O(n)\) instead, and indeed we need to do this in order to pass all test cases within the given time complexity.

Instead, we can track the furthest we can jump, then for each iteration of our outer loop set furthest = max(furthest, i + nums[i]), which is \(O(1)\). Our outer for loop can also be bound by furthest instead of nums.size(). This works because we can never “skip” indices on the way to the furthest we can reach – if we can reach index i, then we can certainly reach indices i - 1, i - 2...1, 0 as well.

bool canJump(vector<int>& nums) {
    int furthest = 0;
    for (int i = 0; i <= furthest; ++i) {
        furthest = max(furthest, i + nums[i]);
        if (furthest >= nums.size() - 1) {
            return true;
        }
    }
    return false;
}

Mildly funny story: I still had the unnecessary memo array from my first incorrect solution, and after getting the solution I tried to see how much memory I saved . A combination of undo commands, copy-paste, and lack of brains resulted in me sending in three failing submissions (including a compile error!) before sending in a correct submission without the memo. For some reason, having that dummy memo array only adds 0.3 MB to memory usage.

This is the last DP problem of the Blind 75. I think I will need to review some harder DP problems in the future; overall, these felt easy and like I wasn’t really being exposed to any new concepts. Not that that’s bad or anything, but I want to try some problems that are a little more jarring and see how I handle them (because no one’s going to throw jump game on their pre-screening assessment).