C++ program to find next Smaller of next Greater in an array

For every element in the array, print the next smaller of the next greater element. Also print -1 for elements who do not either the next greater or next smaller of the next greater.

Examples:

Input:5 7 3 2 1 5 4

Element             Next Greater                   Next smaller of next greater
5                        7                                       3
7                       -1                                      -1
3                        5                                       4
2                        5                                       4
1                        5                                       4
5                       -1                                      -1
4                       -1                                      -1

Output:3 -1 4 4 4 -1 -1

Input:2 1 0 3 2 1 1

Element             Next Greater                      Next smaller of next greater
2                         3                                         2
1                         3                                         2
0                         3                                         2
3                        -1                                        -1
2                        -1                                        -1
1                        -1                                        -1
1                        -1                                        -1

Output: 2 2 2 -1 -1 -1 -1

The approach towards the problem:

One approach to this problem is the brute force approach that is to first find the next greater element and then correspondingly finding the next smaller element for the next greater element. But the time complexity for this would be O(n^2).

But there is a better solution which takes O(n) time which takes the help of stack data structure.

Algorithm:

1) Create an array c[] that will store the indexes of the next greater element of each element and a stack p which will also store indexes.

2)  Now traverse the array but in reverse order. First, we will store the indexes of the next greater element of each element. For that,

a) While p is non-empty and if the topmost element of p is smaller than or equal to a[i] , then pop p.
b)  If p is empty, a[i] has no greater element, that means c[i]=-1  else there exists a next greater element i.e. c[i]=p.top()
c) Now push the current element into the stack i.e. p.push(i)

3) Now find the next smaller element of the already next greater element by creating another array b[] to store this next smaller element. For this repeat step, 1 and 2 but this time we use b[] instead of c[] and we pop from stack p when the top element is greater than or equal to a[i].

4) Now to print them,
if c[i]!=-1 && b[c[i]]!=-1
print a[c[b[i]]]
else print -1

Program to find next smaller of next greater in array in C++

We will make two functions one which would find the next greater element of the present element and the other which would find the next smaller element of this greater element just found and print it. Let’s see it with the help of the code.

#include<bits/stdc++.h>
using namespace std;

//function to find the next greater element
void next_greater(int a[],int n,int m[],char x)
{
    stack<int>p;

    // Traversing the array
    // if x=='+',we find the next greater element of each element
    // else we find the next smaller element of each element
    for(int i=n-1;i>=0;i--)
    {
        //pop when element is smaller than or equal to a[i]
         // (if x==-)
        // and when element is greater than or equal to a[i]
        // (if x==+)
        while(!p.empty() && ((x=='+')? a[p.top()]<=a[i]:
               a[p.top()]>=a[i])) p.pop();
        
        // p.top() is the next greater element and is stored in m[]
        if(!p.empty()) m[i]=p.top();
        
        //if a[i] was greater than all elements of stack
        else m[i]=-1;
        //push the current element in the stack
        p.push(i);
    }
}
//function to get the next smaller of the next
 //greater element for each element
void ans(int a[],int n)
{
    int c[n];  // for indexes of next greater elements
    int b[n];  // for indexes of next smaller of previous greater 
    next_greater(a,n,c,'+'); //for next greater element
    next_greater(a,n,b,'-');  // for next smaller element
    for(int i=0;i<n;i++)
    {
        if(c[i]!=-1 && b[c[i]]!=-1) cout<<a[b[c[i]]]<<" ";
        else cout<<"-1"<<" ";    // no smaller element
    }
}
int main()
{
    int a[]={2,1,0,3,2,1,2};
    int n=7;
    ans(a,n);
}

Output:-

Input: 2 1 0 3 2 1 2
Output:2 2 2 -1 -1 -1 -1

Thank You for reading!!
I hope it helps!