human
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"
Solution in Python:
assistant
#Here is code to find next Smaller of next Greater in an array and the other steps required.
 def nextGreater ( arr , n , next , order ) :
	S = [ ]
	for i in range ( n - 1 , - 1 , - 1 ) :
		while ( S != [ ] and ( arr [ S [ len ( S ) - 1 ] ] <= arr [ i ] if ( order == ' G ' ) else arr [ S [ len ( S ) - 1 ] ] >= arr [ i ] ) ) :
			S . pop ( )
		if ( S != [ ] ) :
			next [ i ] = S [ len ( S ) - 1 ]
		else :
			next [ i ] = - 1
		S . append ( i )
def nextSmallerOfNextGreater ( arr , n ) :
	NG = [ None ] * n
	RS = [ None ] * n
	nextGreater ( arr , n , NG , ' G ' )
	nextGreater ( arr , n , RS , ' S ' )
	for i in range ( n ) :
		if ( NG [ i ] != - 1 and RS [ NG [ i ] ] != - 1 ) :
			print ( arr [ RS [ NG [ i ] ] ] , end = " ▁ " )
		else :
			print ( " - 1" , end = " ▁ " )
if __name__ == " _ _ main _ _ " :
	arr = [ 5 , 1 , 9 , 2 , 5 , 1 , 7 ]
	n = len ( arr )
	nextSmallerOfNextGreater ( arr , n )