Find next Smaller of next Greater in an array | C ++ Program to find Right smaller element of next greater element ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void nextGreater ( int arr [ ] , int n , int next [ ] , char order ) { stack < int > S ; for ( int i = n - 1 ; i >= 0 ; i -- ) { while ( ! S . empty ( ) && ( ( order == ' G ' ) ? arr [ S . top ( ) ] <= arr [ i ] : arr [ S . top ( ) ] >= arr [ i ] ) ) S . pop ( ) ; if ( ! S . empty ( ) ) next [ i ] = S . top ( ) ; else next [ i ] = -1 ; S . push ( i ) ; } } void nextSmallerOfNextGreater ( int arr [ ] , int n ) { int NG [ n ] ; int RS [ n ] ; nextGreater ( arr , n , NG , ' G ' ) ; nextGreater ( arr , n , RS , ' S ' ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( NG [ i ] != -1 && RS [ NG [ i ] ] != -1 ) cout << arr [ RS [ NG [ i ] ] ] << " ▁ " ; else cout << " - 1" << " ▁ " ; } } int main ( ) { int arr [ ] = { 5 , 1 , 9 , 2 , 5 , 1 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; nextSmallerOfNextGreater ( arr , n ) ; return 0 ; }