# Jump Game

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

Discussion

What do we know? You can jump up to nums[i] steps, which means there are many combinations that may or may not get you there.
We can use backtracking to find a solution. The downside is that it’s recursive and thus heavy on function call stack. We can optimize the timing by caching (top down dynamic programming) but it may still not be optimal.
We can use greedy algorithm to get there more efficiently. Note that this approach as described here relies on being able to jump up to nums[i] steps; if it was a specific step or specific combination of steps, this wouldn’t work. The above approach on backtracking with some modifications (on what steps are allowed) would still work.

Recursive Solution – Backtracking and Dynamic Programming

At each step, we can take up to the steps indicated by the array at that index. This means we can take one of 1,2,..,k steps.
We can use recursion and backtracking to test all of these possibilities to find if any of those possibilities end up with a solution. At the starting point (first index), we check if any of the steps we take can eventually lead us to the end. If it does, we return true. If not, we return false.

``````var canJump = function(nums, index=0, cache=[]) {
if (cache[index]) {
}
if (index===nums.length-1) {
return true; //got to end
}
for (let i=1;i<=nums[index];i++) {
cache[index+i]=canJump(nums,index+i,cache);
if (cache[index+i]) {
return true; //this is a path that could lead to the end
}
}
return false;
};``````

Greedy Algorithm Solution

Let’s think about it from the other end. How can we result in a jump to the last index?
We benefit here from the fact that at each index, we can jump any distance up to the max jump. Which means that any prior index that can jump to a target index, it can also jump to a closer index. This would not be possible if instead of max jump for example it was a predetermined jump distance.
Thus when we find an index that can reach our target, our new goal is simply reaching that new index. That index which gets us to our target thus becomes our new target!

``````var canJump = function(nums) {
let target=nums.length-1;
for (let i=nums.length-2;i>=0;i--) {
const distance=target-i; //distance from current index to target index
//check if we can reach target from here
if (nums[i]>=distance) {
target=i;
}
}
if (target===0) {
return true; //the first step has a pathway to end
}
return false;
};``````