https://neetcode.io/problems/jump-game-ii?list=neetcode150
initial
im thinking like the first step is necessary so within the first steps range, we find the maximum value and take that and increment ans and with that new max value we traverse up until that range and if we meet the end of list we just return ans but else we again take the maximum value and update it is that right way
but i was using a nested double while loop that made the impl much harder. Instead, we can just use the iter i pointer as the starting index of our jump and recording the maximum possible jump range with i+nums[i]. If we meet the maximum current end range, we increment jump and update the maximum current end range with the max poss jump range.
sol
class Solution {
public int jump(int[] nums) {
int furthest=0;
int ans=0;
int cur_end=0;
for(int i =0;i<nums.length-1;i++){
furthest=Math.max(furthest,i+nums[i]);
if(i==cur_end){
ans+=1;
cur_end=furthest;
}
}
return ans;
}
}
complexity
n time 1 space
