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 program
def nextGreater ( arr , n , next , order ) : NEW_LINE INDENT S = [ ] NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT while ( S != [ ] and ( arr [ S [ len ( S ) - 1 ] ] <= arr [ i ] if ( order == ' G ' ) else arr [ S [ len ( S ) - 1 ] ] >= arr [ i ] ) ) : NEW_LINE INDENT S . pop ( ) NEW_LINE DEDENT if ( S != [ ] ) : NEW_LINE INDENT next [ i ] = S [ len ( S ) - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT next [ i ] = - 1 NEW_LINE DEDENT S . append ( i ) NEW_LINE DEDENT DEDENT def nextSmallerOfNextGreater ( arr , n ) : NEW_LINE INDENT NG = [ None ] * n NEW_LINE RS = [ None ] * n NEW_LINE nextGreater ( arr , n , NG , ' G ' ) NEW_LINE nextGreater ( arr , n , RS , ' S ' ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( NG [ i ] != - 1 and RS [ NG [ i ] ] != - 1 ) : NEW_LINE INDENT print ( arr [ RS [ NG [ i ] ] ] , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " - 1" , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 1 , 9 , 2 , 5 , 1 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE nextSmallerOfNextGreater ( arr , n ) NEW_LINE DEDENT