The next greater element is a problem in which we have given an array. This array containing N values(may be positive or negative). We need to find the first greater_element in the given array on its right side. If there is no greater_element then take -1.
Table of Contents
Input Format
First-line containing single integer value N. Second-line containing N integer numbers.
Output Format
Print the next greater element for every number store in an array. Note: Order of element may change.
Constraints
- 1<=N<=1000000
- |a[i]|<=1000000000.
Example Input-1: 9 4 3 6 2 -1 4 -5 3 2
Example Output-1: 3 -> 6 4 -> 6 -1 -> 4 2 -> 4 -5 -> 3 2 -> -1 3 -> -1 4 -> -1 6 -> -1
Explanation: By the use of stack we find the next greater element of every number. Firstly we push the first number into a stack. Now, iterate all the remaining values from index 1 to n-1. If the value at which index we are currently is smaller than or equal to the value of the top of the stack then we push that into the stack. If the value at which index we are currently is greater than the value of the top of the stack. Then we pop the elements from the stack and set the next greater element for poped element which we traverse. Repeat it till we not get the condition top of the stack is greater than the current element. Find it for all the values. For better understanding see the below example step by step.
Algorithm For Next greater element
Algorithm:
Step:1 Push the First value of array into a stack.
Step:2 Traverse all the nodes one by one and follow the conditions:
i) Mark the current element as traverse.
ii) If the stack is not empty then, compare the top of the stack with the traverse.
If traverse is greater then pop element from the stack and assigns NGE of pop element as traverse else push traverse into stack.
iii) Repeat step 2.i and 2.ii till we traverse all the values of array.
Step:3 The remaining values/elements in the array have no element which is NGE. So, we assign -1 as NGE of all remaining values.
Step:4 Print the NGE values of each node.Implementation
/*C++ Implementation of Next greater element problem*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
/*take the input n*/
cin>>n;
int a[n];
/*take input array of n numbers*/
int nge[n];
/*vector use to store the answer*/
vector<pair<int ,int > > v;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
stack<int> s;
/*push first element into sack*/
s.push(a[0]);
/*traverse rest of others elements*/
for(int i=1;i<n;i++)
{
/*current element*/
int traverse=a[i];
/*element at top of stack*/
int top=s.top();
/*if traverse is less than top of stack*/
if(traverse<top)
{
s.push(traverse);
}
else/*if traverse is greater than top of stack*/
{
/*repeat till traverse greater than top of stack*/
while(s.size()>0&&s.top()<traverse)
{
int x=s.top();
s.pop();
v.push_back({x,traverse});
}
/*if stack is empty then insert traverse*/
if(s.size()==0)
{
s.push(traverse);
}
/*add traverse into stack*/
if(traverse<s.top())
{
s.push(traverse);
}
}
}
/*after traversing all element we check stack contain values or not. If stack contain some
values then pop them one by one and assign NGE as -1 to all elements of stack*/
while(s.size()>0)
{
int x=s.top();
s.pop();
v.push_back({x,-1});
}
/*print the answer*/
for(int i=0;i<v.size();i++)
{
cout<<v[i].first<<" -> "<<v[i].second<<endl;
}
return 0;
}Input: 4 12 14 22 4
Output: 12 -> 14 14 -> 22 4 -> -1 22 -> -1
Time Complexity
O(N) because we do traversal of all the elements of an array and perform the operation. By the use of vector, we print the result in the linear traversal.
Space Complexity
O(N) because we use vector which stores n pairs of integer(pair<int, int>) and an array for storing the N numbers.