Find next Smaller of next Greater in an array | function find Next greater element ; create empty stack ; Traverse all array elements in reverse order order == ' G ' we compute next greater elements of every element order == ' S ' we compute right smaller element of every element ; Keep removing top element from S while the top element is smaller then or equal to arr [ i ] ( if Key is G ) element is greater then or equal to arr [ i ] ( if order is S ) ; store the next greater element of current element ; If all elements in S were smaller than arr [ i ] ; Push this element ; Function to find Right smaller element of next greater element ; stores indexes of next greater elements ; stores indexes of right smaller elements ; Find next greater element Here G indicate next greater element ; Find right smaller element using same function nextGreater ( ) Here S indicate right smaller elements ; If NG [ i ] = = - 1 then there is no smaller element on right side . We can find Right smaller of next greater by arr [ RS [ NG [ i ] ] ] ; Driver code
function nextGreater ( arr , next , order ) { let stack = [ ] ; for ( let i = arr . length - 1 ; i >= 0 ; i -- ) { while ( stack . length != 0 && ( ( order == ' ' ) ? arr [ stack [ stack . length - 1 ] ] <= arr [ i ] : arr [ stack [ stack . length - 1 ] ] >= arr [ i ] ) ) stack . pop ( ) ; if ( stack . length != 0 ) next [ i ] = stack [ stack . length - 1 ] ; else next [ i ] = - 1 ; stack . push ( i ) ; } } function nextSmallerOfNextGreater ( arr ) { let NG = new Array ( arr . length ) ; let RS = new Array ( arr . length ) ; for ( let i = 0 ; i < arr . length ; i ++ ) { NG [ i ] = 0 ; RS [ i ] = 0 ; } nextGreater ( arr , NG , ' ' ) ; nextGreater ( arr , RS , ' ' ) ; for ( let i = 0 ; i < arr . length ; i ++ ) { if ( NG [ i ] != - 1 && RS [ NG [ i ] ] != - 1 ) document . write ( arr [ RS [ NG [ i ] ] ] + " " ) ; else document . write ( " " ) ; } } let arr = [ 5 , 1 , 9 , 2 , 5 , 1 , 7 ] ; nextSmallerOfNextGreater ( arr ) ;