Jump Game II

/*

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;

    }

}