Find next Smaller of next Greater in an array

Find next Smaller of next Greater in an array

Given array of integer, find the next smaller of next greater element of every element in array.

Note : Elements for which no greater element exists or no smaller of greater element exist, print -1.

Examples:

Input : arr[] = {5, 1, 9, 2, 5, 1, 7}
Output:          2  2 -1  1 -1 -1 -1
Explanation :  
Next Greater ->      Right Smaller 
   5 ->  9             9 ->  2 
   1 ->  9             9 ->  2
   9 -> -1            -1 -> -1
   2 ->  5             5 ->  1
   5 ->  7             7 -> -1
   1 ->  7             7 -> -1
   7 -> -1            -1 -> -1 

Input  : arr[] = {4, 8, 2, 1, 9, 5, 6, 3}
Output :          2  5  5  5 -1  3 -1 -1 

Solution: 

void nextGreater(int[] arr,int n,int[] next,char order)

{

    // create empty stack

    Stack<Integer> S = new 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

    for (int i=n-1; i>=0; i--)

    {

        // 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)

        while (!S.empty() &&

              ((order=='G')? arr[S.peek()] <= arr[i]:

                           arr[S.top()] >= arr[i]))

            S.pop();

 

        // store the next greater element of current element

        if (!S.empty())

            next[i] = S.peek();

 

        // If all elements in S were smaller than arr[i]

        else

            next[i] = -1;

 

        // Push this element

        S.push(i);

    }

}

 

// Function to find Right smaller element of next greater

// element

void nextSmallerOfNextGreater(int arr[], int n)

{

    int NG[n]; // stores indexes of next greater elements

    int RS[n]; // stores indexes of right smaller elements

 

    // Find next greater element

    // Here G indicate next greater element

// NG will store indexes of next greater element

    nextGreater(arr, n, NG, 'G');

 

    // Find right smaller element

    // using same function nextGreater()

    // Here S indicate right smaller elements

// RS will store indexes of next smaller element

    nextGreater(arr, n, RS, 'S');

 

    // 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]]]

    for (int i=0; i< n; i++)

    {

        if (NG[i] != -1 && RS[NG[i]] != -1)

            System.out.println(arr[RS[NG[i]]]+" ");

        else

            System.out.println("-1");

    }

}