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.
Starting at index 0, the number of indexes you can jump from 0 is given by 0 .. array[0]. You will always jump to array[array.length-1], aka the last index of the array. The question is what is the least number of times you need to perform a jump.
This very similar to my last post. Both question deal about the minimum of all permutations with specific conditions for determining the progress. I encourage you to at least familiarize what I did for the brute force of last question so that the rest of article makes sense.
Below is my first attempt brute force:
var jump = function(nums) {
let min = Number.MAX_SAFE_INTEGER;
function recur(index, counts) {
if(index >= nums.length-1) {
min = Math.min(min, counts);
}
let steps = nums[index];
while (steps) {
recur(index+steps, counts+1);
steps--;
}
}
recur(0,0);
return min;
};
If you were familiar with my brute force approach in the min cost question, this will feel extremely similar. After initializing the min variable with MAX_SAFE_INTEGER, all there is left to do is to call on the recursion. The end condition of recursion is when we have reached beyond the length of array, exactly same as min cost condition. The recursion progresses forward differently by having a while loop that decrements the number of indexes jumped each time. This is going through all the possibilities for each square we touch. Therefore after going through all the permutations, the min variable will contain the minimal number of count for the times a particular recursion path took to reach to the end.
The problem with this solution is the same as my brute force min cost: there is nothing that can be remembered at each step. The greedy algorithm here is then the same: remember the min step to reach to each index as we add in one more index each time.
So let's see how can we improve on this:
1.) we will need a memoization:
const memo = (new Array(nums.length)).fill(Number.SAFE_MAX_INTEGER);
it should work as each index in memo[] corresponds to the same index in nums. However, the value for each index in memo will represent the minimal jumps to get to it. So we should:
memo[0]= 0, as the first index requires no jumping to.
2.) Progress linearly. For each index we examine in nums, we first retrieve this current index's minimal jump to it. Next, since nums[index] = number of jumps we can perform, we loop through this number and compare with the memo's current minimal record. We modify the memo as needed:
nums.forEach(function(numJumps, index){
const currentNum = memo[index];
for(let i=1; i<numJumps; i++) {
const jumpedToIndex = index+i;
memo[jumpedToIndex] = min(memo[jumpedToIndex], currentNum+1)
}
})
This should allow us to build a memo where each index has a record of the minimal number of jumps required to get to it from index 0, therefore, the last index of the memo should be our answer
3.) return memo[memo.length-1];
Wow to my surprise I guess I really understood the question, with some modification, such as Math.min instead of min, and forgetting that the jumpedToIndex can be more than the length, I got an accepted submission message!!
below is the optimal solution:
var jump = function(nums) {
let newMax = 0;
let jump = 0;
let oldMax = 0;
for (let i=0;i<nums.length-1;i++) {
newMax = Math.max(newMax, i+nums[i]);
if (i == oldMax) {
jump++;
oldMax = newMax;
}
}
return jump;
};
Turns out this wasn't much of a DP problem at a... fuck... This is because the problem has an interesting special property: since it progress linearly and jumps from each index is continuous integer, we can't ever miss an index that has further reach.
Say index 0 has a value of 5, it means we can jump from 1 - 5. There is a number, say 3, that can has a bigger number of jumps than any other index between 1 - 5. So let's say nums[3] = 10, and all others are 1. When we progress linearly forward, we will surely hit 3 and get the newMax to be 3 + 10 = 13. The variable i will also hit oldMax for sure, so that'll increment jump and set oldMax to newMax.
The question is the bizarre if(i==oldMax) logic. Why would it always accurately account for the minimal number of jumps necessary. The reason is that let's say:
1.) nums[0] >= nums.length-1, we are done! It will accurately add 1 to jump since oldMax and i are both 0 to start with.
2.) When nums[0] < nums.length-1, it mean that there is at least one more jump that will reach further toward the end. The reason why i==oldMax would work is because when nums[0], oldMax = nums[0]. At this point two things can happen:
no index goes further than at nums[0]: therefore at i == nums[0] == oldMax, we'll necessarily jump again to so index further toward the end
Some index, x, between 1 - nums[0] goes further than i == nums[0]: this means that there is one jump from 0 to x, and x to the new newMax. In this instance oldMax < x < nums.length-1, so i must hit oldMax before going to x, thus accurately jump++.
It's also quite crazy that this algorithm also takes care the cases when the jumps reaches further than the end. It'll be pretty unreasonable to come up with this algorithm at interview, but hey that's why some of these crazy dudes get paid more than 99% of the population.
Lessons learned for DP:
1.) determine if incrementally increasing subproblem can reach the solution, idk how to do this but seems to be a pattern for minimal/maximal type.
2.) memoization is always about the matrix we care about, such as the minimal step or minimal cost.
3.) we should probably always progress linearly if it is obvious a DFS approach can solve it anyways. Going backwards or forward does not really matter. There are cases that backwards is more optimal, how fucking great ...
Let me know anything on your mind after reading through this, THANKS!
Top comments (0)