DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Jump Game II

Problem

/*
TC: O(n), outer loop is just for checking if r<n-1, inner loop is doing the
traversal for n elements
This is greedy because in every iteration we are trying to find out the farthest index that we can jump to.
example :
nums = [2,3,1,1,4]

for the index 0 , we can jump to index 1 or we can jump to index 2
So range for the first jump (jump = 1) becomes index: 1,2
from index 1 we can jump to index 2,3,4 ( if we jump to index 2 jump = 2, if we jump to index 3 jump = 2 and if we jump to index 4 
jump =2, so we want to minimize the countOfJump and maximize the range of jump which is index 4 in this case)
We can have left and right pointer intialized with 0, then we can iterate left till right to find the max index that can be reached, then 
update left and right to point to new range
Do it till the n-1 index is reached
*/

class Solution {
    public int jump(int[] nums) {
        int left =0,right =0;
        int jump = 0;
        while(right<nums.length-1){
            int farthest = 0;
            for(int i =left;i<=right;i++){
                farthest = Integer.max(farthest, i+ nums[i]);
            }
            //now update left and right to point to new range
            left = right+1;
            right  =farthest;

            jump++;
        }
        return jump;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)