Simple O(N) solution


  • 0
    G

    '''
    public int jump(int[] nums) {

        if(nums == null || nums.length <=1) return 0;
        int i=1;
        int start = 0;
        int end = nums[0];
        
        while(end<nums.length-1){
            
            int maxIndex = 0;
            
            for(int j = start;j<=end;j++){
                if(nums[j] == 0) continue;
                if(j + nums[j] >= nums.length - 1){
                    return i+1;
                }
                // Maximum index that can be reached from any value between start to end
                maxIndex = Math.max(maxIndex, j + nums[j]);
            }
            
            start = end;
            end = maxIndex;
            i++;
        }
        return i;
    }
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.