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 code
using System ; using System . Collections . Generic ; public class GFG { public static void nextGreater ( int [ ] arr , int [ ] next , char order ) { Stack < int > stack = new Stack < int > ( ) ; for ( int i = arr . Length - 1 ; i >= 0 ; i -- ) { while ( stack . Count != 0 && ( ( order == ' G ' ) ? arr [ stack . Peek ( ) ] <= arr [ i ] : arr [ stack . Peek ( ) ] >= arr [ i ] ) ) stack . Pop ( ) ; if ( stack . Count != 0 ) next [ i ] = stack . Peek ( ) ; else next [ i ] = - 1 ; stack . Push ( i ) ; } } public static void nextSmallerOfNextGreater ( int [ ] arr ) { int [ ] NG = new int [ arr . Length ] ; int [ ] RS = new int [ arr . Length ] ; nextGreater ( arr , NG , ' G ' ) ; nextGreater ( arr , RS , ' S ' ) ; for ( int i = 0 ; i < arr . Length ; i ++ ) { if ( NG [ i ] != - 1 && RS [ NG [ i ] ] != - 1 ) Console . Write ( arr [ RS [ NG [ i ] ] ] + " ▁ " ) ; else Console . Write ( " - 1 ▁ " ) ; } } public static void Main ( ) { int [ ] arr = { 5 , 1 , 9 , 2 , 5 , 1 , 7 } ; nextSmallerOfNextGreater ( arr ) ; } }