Minimum number of jumps to reach end | Java program to find Minimum number of jumps to reach end ; Returns Minimum number of jumps to reach end ; jumps [ 0 ] will hold the result ; Minimum number of jumps needed to reach last element from last elements itself is always 0 ; Start from the second element , move from right to left and construct the jumps [ ] array where jumps [ i ] represents minimum number of jumps needed to reach arr [ m - 1 ] from arr [ i ] ; If arr [ i ] is 0 then arr [ n - 1 ] can 't be reached from here ; If we can direcly reach to the end point from here then jumps [ i ] is 1 ; Otherwise , to find out the minimum number of jumps needed to reach arr [ n - 1 ] , check all the points reachable from here and jumps [ ] value for those points ; initialize min value ; following loop checks with all reachable points and takes the minimum ; Handle overflow ; or Integer . MAX_VALUE ; Driver Code
class GFG { static int minJumps ( int arr [ ] , int n ) { int [ ] jumps = new int [ n ] ; int min ; jumps [ n - 1 ] = 0 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] == 0 ) jumps [ i ] = Integer . MAX_VALUE ; else if ( arr [ i ] >= n - i - 1 ) jumps [ i ] = 1 ; else { min = Integer . MAX_VALUE ; for ( int j = i + 1 ; j < n && j <= arr [ i ] + i ; j ++ ) { if ( min > jumps [ j ] ) min = jumps [ j ] ; } if ( min != Integer . MAX_VALUE ) jumps [ i ] = min + 1 ; else jumps [ i ] = min ; } } return jumps [ 0 ] ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 6 , 1 , 0 , 9 } ; int size = arr . length ; System . out . println ( " Minimum ▁ number ▁ of " + " ▁ jumps ▁ to ▁ reach ▁ end ▁ is ▁ " + minJumps ( arr , size ) ) ; } }