Next Smaller Element | prints element and NSE pair for all elements of arr [ ] of size n ; push the first element to stack ; iterate for rest of the elements ; if stack is not empty , then pop an element from stack . If the popped element is greater than next , then a ) print the pair b ) keep popping while elements are greater and stack is not empty ; push next to stack so that we can find next smaller for it ; After iterating over the loop , the remaining elements in stack do not have the next smaller element , so print - 1 for them ; Driver Code ;
def printNSE ( arr , n ) : NEW_LINE INDENT s = [ ] NEW_LINE mp = { } NEW_LINE s . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( len ( s ) == 0 ) : NEW_LINE INDENT s . append ( arr [ i ] ) NEW_LINE continue NEW_LINE DEDENT while ( len ( s ) != 0 and s [ - 1 ] > arr [ i ] ) : NEW_LINE INDENT mp [ s [ - 1 ] ] = arr [ i ] NEW_LINE s . pop ( ) NEW_LINE DEDENT s . append ( arr [ i ] ) NEW_LINE DEDENT while ( len ( s ) != 0 ) : NEW_LINE INDENT mp [ s [ - 1 ] ] = - 1 NEW_LINE s . pop ( ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , " - - - > " , mp [ arr [ i ] ] ) NEW_LINE DEDENT DEDENT arr = [ 11 , 13 , 21 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE printNSE ( arr , n ) NEW_LINE s NEW_LINE