Next Smaller Element | A Stack based C ++ program to find next smaller element for all array elements ; prints NSE for elements of array arr [ ] of size n ; iterate for rest of the elements ; while stack is not empty and the top element is greater than next a ) NSE for top is next , use top 's index to maintain original order b) pop the top element from stack ; push next to stack so that we can find NSE for it ; After iterating over the loop , the remaining elements in stack do not have any NSE , so set - 1 for them ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printNSE ( int arr [ ] , int n ) { stack < pair < int , int > > s ; vector < int > ans ( n ) ; for ( int i = 0 ; i < n ; i ++ ) { int next = arr [ i ] ; if ( s . empty ( ) ) { s . push ( { next , i } ) ; continue ; } while ( ! s . empty ( ) && s . top ( ) . first > next ) { ans [ s . top ( ) . second ] = next ; s . pop ( ) ; } s . push ( { next , i } ) ; } while ( ! s . empty ( ) ) { ans [ s . top ( ) . second ] = -1 ; s . pop ( ) ; } for ( int i = 0 ; i < n ; i ++ ) { cout << arr [ i ] << " ▁ - - - > ▁ " << ans [ i ] << endl ; } } int main ( ) { int arr [ ] = { 11 , 13 , 21 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printNSE ( arr , n ) ; return 0 ; }