This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.
This problem is a true medium difficulty. I definitely recommend people to try this when you feel warm in the DP pool.
The question is given an array of integers >= 0, figure out whether you can "jump" from the first index to the last. You start at index=0, and the max number of indexes you can jump from 0 is array[0]. Note this means you can do 0 .. array[0] number of jumps. You likewise jump via this logic until you hit a dead end where array[index] = 0 or successfully end on index = array.length-1.
The brute force answer for this is relatively simple: run a recursion from index 0, where at each iteration we run through all possibilities of its number of jumps. So this is DFS and see if there is path from the root node all the way to the target leaf:
var canJump = function(nums) {
if (nums.length === 1) { return true; }
if (nums.every(Boolean)) { return true }
let hasPath = false;
function recur (index) {
if(hasPath) { return true } //stop recursion immediately
if (index >= nums.length-1) {
hasPath = true;
return true;
}
else if(nums[index] === 0) {
return false;
}
else {
let jumps = nums[index];
while (jumps) {
recur(index+jumps);
jumps--;
}
}
}
recur(0);
return hasPath;
};
Next we should move on to the memoized version of this, this is because once we run the recursion on an index once, we already know whether or not that index can ever reach to the end. So future encounter of the same index can just terminate with the memoized result:
var canJump = function(nums) {
if (nums.length === 1) { return true; }
if (nums.every(Boolean)) { return true }
const memo = [];
let hasPath = false;
function recur (index) {
if (memo.hasOwnProperty(index)) return memo[index];
if (index >= nums.length-1 || hasPath) {
hasPath = true;
return true;
}
else if(nums[index] === 0) {
return false;
}
else {
let jumps = nums[index];
while (jumps && !hasPath) {
recur(index+jumps);
jumps--;
}
memo[index] = hasPath;
}
}
recur(0);
return hasPath;
};
this would pass submission, surprisingly tbh, but it ain't good enough, WE WANT IT FASTER!!!!!
Usually at this point the answer has something to do with bottom-up, aka going from the other direction, or math ... hopefully never math.
However, calm down before going down on writing the code, it is always a good habit to approach the problem abstractly/mathematically so that we might be able to discover something that would improve performance and maybe even make the code simpler as added bonus.
So let's take index = a, and it can path to the end, we would remember this index somehow. When we go to a-1, it is basically guaranteed that it will jump to a, unless of array[a-1] === 0. This means that if there is a path to end from a, then the question for all the indexes before a is that whether they can reach a somehow.
All indexes can reach a if and only if b + array[b] >= a. This is because b can jump from b+1, b+2 ... b+array[b], so if b + array[b] >= a, then there must be some number where b + x == a, where x <= array[b].
Therefore we do not really need to go through all of the indexes from i to i + array[i]. If we have a, then the it's just whether i + array[i] >= a. Now what if there is a number between i and a that also paths to the end? In this cause, we just need to change the condition to whether i + array[i] >= j, where j paths to end and is between i and a. Would we always find j? The answer is yes, because we should be walking from right to left and check every index, there is no way for us to skip indexes and be 100% confident that the code would work. Therefore we will always find j between i and a.
There is another quick question what if there exists index y that does not path to end and comes after a. So i -> a -> y. Is it possible that i skips a to y and therefore cannot end ? The answer is no since the number of possible jumps is a continuous integer interval. The only possible path failure is i path terminates before a.
Now we just need to take care of the initial condition: how do we find "a" if "a" is the very first index that will path to the end? The answer is pretty instinctive if our heads aren't spinning too much yet. This is why it's always good to start with the brute force solution since it'll always contain part of the optimal solution so you have to worry less. The answer is if a + array[a] >= array.length-1, the only condition we had in brute force.
Therefore in our bottom up code, we need to:
1.) check if a + array[a] >= array.length-1
2.) check if a + array[a] >= path_to_end_index
3.) return whether path_to_end_index === 0 in the end.
var canJump = function(nums) {
if (nums.length === 1) { return true; }
let successfulIndexes = null;
let index = nums.length-1;
while(index > -1) {
if(successfulIndexes !=null && (nums[index] + index) >= successfulIndexes) {
successfulIndexes = index;
}
else if ((nums[index] + index) >= nums.length-1){
successfulIndexes = index;
}
index--;
}
return successfulIndexes === 0;
};
lessons learned:
1.) bottom up solution would look vastly different from recursion solution, delete the recursion code once you see it is possible to do bottom-up (I spent too much time trying to mold my recursion solution into bottom-up).
2.) recursion solution implies bottom up ? This seems to make sense since DFS is in a sense a "bottom-up" process. If anyone feels the same or know it is true comment below thanks!
Let me know anything on your mind after reading through this, THANKS!
Top comments (0)