Minimum jumps required to reach all array elements using largest element | Function to find next greater element to left and right of current element ; Starting l and r from previous and the next element of the current element ; FInd the next greater element to the left ; Find the next greater element to the right ; Return l and r in the form of array of size 2 ; Function to find the minimum jumps required to reach to all elements from the largest element ; Stores the mapping from index to the element in array A [ ] ; Stores largest array element ; Find the two indices l , r such that A [ l ] > A [ i ] < A [ r ] and l < i < r using expand function ; sorting A in descending order ; Stores the resultant minimum jumps required ; Check if the current element is largest or not ; Find the answer to the current element ; Update the resultant minimum jumps for the current element ; Return the result ; Driver Code ; Prlet the result
function expand ( idx , A ) { let l = idx - 1 ; let r = idx + 1 ; while ( l >= 0 ) { if ( A [ idx ] > A [ l ] ) { -- l ; } else { break ; } } if ( l < 0 l == idx ) { l = - 2 ; } while ( r < A . length ) { if ( A [ idx ] > A [ r ] ) { ++ r ; } else { break ; } } if ( r >= A . length r == idx ) { r = - 2 ; } return [ l , r ] ; } function minJumps ( N , A ) { let ans = new Array ( N ) . fill ( 0 ) ; let mp = new Map ( ) ; let iToA = new Map ( ) ; let AToi = new Map ( ) ; let big = A [ 0 ] ; for ( let i = 0 ; i < N ; ++ i ) { big = Math . max ( big , A [ i ] ) ; mp . set ( i , expand ( i , A ) ) ; iToA . set ( i , A [ i ] ) ; AToi . set ( A [ i ] , i ) ; } A . sort ( ( a , b ) => - a + b ) ; for ( let i = 0 ; i < A . length ; ++ i ) { let m ; if ( A [ i ] == big ) { let cur = AToi . get ( A [ i ] ) ; ans [ cur ] = 0 ; continue ; } let cur = AToi . get ( A [ i ] ) ; let l = mp . get ( cur ) [ 0 ] ; let r = mp . get ( cur ) [ 1 ] ; if ( l >= 0 && r < N ) { m = Math . min ( ans [ l ] , ans [ r ] ) + 1 ; } else if ( l < 0 && r < N ) { m = ans [ r ] + 1 ; } else if ( l >= 0 && r >= N ) { m = ans [ l ] + 1 ; } ans [ cur ] = m ; } return ans ; } let arr = [ 5 , 1 , 3 , 4 , 7 ] ; let N = arr . length ; let out = minJumps ( N , arr ) ; for ( it of out ) document . write ( it + " " ) ;