Jump Game | LeetCode 55

The key to this is realizing that to get to test if you can get to a target index from the current index, you can add the current index to its value. For instance, if index 3 has the value of 5, you add 3 and 5, which gives you 8. If your target index is greater than 8, you can’t get to it from index 3.

Using that knowledge, we can start iterating to the left from the final index of the array. If the index to the left has an index + value that is greater than or equal to the target index (which is the final index, in this case), our new target index will be the index to the left of the final index. If the value of the index to the left of the final index (plus the index itself) is not greater than or equal to the final index, the final index remains the target index.

Either way, we keep moving left. We apply that logic for each iteration, updating the target index if we can get to it from an index to the left of it. If we are able to update the target index to the zeroth index, it means we have found a path from the final index to the zeroth index, which means there is at least one path from the zeroth index to the final index.

AFFILIATE LINKS

Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard

Here is the full implementation.

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let lastValidIndex = nums.length - 1;
    
    for (let i = nums.length - 1; i >= 0; i--) {
        if (i + nums[i] >= lastValidIndex) {
            lastValidIndex = i;
        }
    }
        
    return lastValidIndex === 0;
};