Find next Smaller of next Greater in an array | Java 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
import java . util . Stack ; public class Main { public static void nextGreater ( int arr [ ] , int next [ ] , char order ) { Stack < Integer > stack = new Stack < > ( ) ; for ( int i = arr . length - 1 ; i >= 0 ; i -- ) { while ( ! stack . isEmpty ( ) && ( ( order == ' G ' ) ? arr [ stack . peek ( ) ] <= arr [ i ] : arr [ stack . peek ( ) ] >= arr [ i ] ) ) stack . pop ( ) ; if ( ! stack . isEmpty ( ) ) 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 ) System . out . print ( arr [ RS [ NG [ i ] ] ] + " ▁ " ) ; else System . out . print ( " - 1 ▁ " ) ; } } public static void main ( String args [ ] ) { int arr [ ] = { 5 , 1 , 9 , 2 , 5 , 1 , 7 } ; nextSmallerOfNextGreater ( arr ) ; } }