45. Jump Game II Leetcode Java

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Solution:

Dynamic programming

Using a variable to track the maximum index that current step can reach, and during the current step, calculate the maximum index that next step can reach. When it hits the maximum index of current step, update the current maximum to calculated next maximum index. When the maximum index >= A.length, return the steps.
Time complexity: O(n)

 public int jump(int[] A) {  
     if(A==null || A.length<2) return 0;  
     int next=0;  
     int step=0;  
     int cur=0;  
     for(int i=0;i<A.length&&i<=cur;i++){  
       cur=Math.max(cur,i+A[i]);  
       if(cur>=A.length-1) return step+1;  
       if(i==next){  
         next=cur;  
         step++;  
       }  
     }  
     return -1;  
   }