Minimum jumps required to reach all array elements using largest element | C ++ program for the above approach ; 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 ; Print the result
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ar  array NEW_LINE ar < int , 2 > expand ( int idx , vector < int > & A ) { int l = idx - 1 ; int r = idx + 1 ; while ( l >= 0 ) { if ( ( int ) ( A [ idx ] ) > A [ l ] ) { -- l ; } else { break ; } } if ( l < 0 l == idx ) { l = -2 ; } while ( r < ( int ) ( A . size ( ) ) ) { if ( ( int ) A [ idx ] > A [ r ] ) { ++ r ; } else { break ; } } if ( r >= ( int ) ( A . size ( ) ) r == idx ) { r = -2 ; } return { l , r } ; } vector < int > minJumps ( int N , vector < int > & A ) { vector < int > ans ( N , 0 ) ; map < int , ar < int , 2 > > mp ; map < int , int > iToA ; map < int , int > AToi ; int big = A [ 0 ] ; for ( int i = 0 ; i < N ; ++ i ) { big = max ( { big , A [ i ] } ) ; mp [ i ] = expand ( i , A ) ; iToA [ i ] = A [ i ] ; AToi [ A [ i ] ] = i ; } sort ( A . begin ( ) , A . end ( ) , greater < int > ( ) ) ; for ( int i = 0 ; i < A . size ( ) ; ++ i ) { int m ; if ( A [ i ] == big ) { int cur = AToi [ A [ i ] ] ; ans [ cur ] = 0 ; continue ; } int cur = AToi [ A [ i ] ] ; int l = mp [ cur ] [ 0 ] ; int r = mp [ cur ] [ 1 ] ; if ( l >= 0 && r < N ) { m = 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 ; } int main ( ) { vector < int > arr = { 5 , 1 , 3 , 4 , 7 } ; int N = arr . size ( ) ; vector < int > out = minJumps ( N , arr ) ; for ( auto & it : out ) cout << it << ' ▁ ' ; return 0 ; }