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!
Leave a Reply