Hello Everyone,
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1. The next greater elements should be printed in same order as input array.
Examples:
Input : arr = [4, 5, 2, 25}
Output : 5 25 25 -1Input : arr = [4, 5, 2, 25, 10}
Output : 5 25 25 -1 -1
Approach
- In this approach we have started iterating from the last element(nth) to the first(1st) element
The benefit is that when we arrive at a certain index his next greater element will be already in stack, and we can directly get this element while at the same index. - After reaching a certain index we will pop the stack till we get the greater element on top from the current element and that element will be the answer for current element
- If stack gets empty while doing the pop operation then the answer would be -1
Then we will stored the answer in an array for the current index.
Below is the implementation of above approach:
// A Stack based C++ program to find next
// greater element for all array elements
// in same order as input.
#include <bits/stdc++.h>
using namespace std;
/* prints element and NGE pair for all
elements of arr[] of size n */
void printNGE( int arr[], int n)
{
stack< int > s;
int arr1[n];
// iterating from n-1 to 0
for ( int i = n - 1; i >= 0; i--)
{
/*We will pop till we get the
greater element on top or stack gets empty*/
while (!s.empty() && s.top() <= arr[i])
s.pop();
/*if stack gots empty means there
is no element on right which is greater
than the current element.
if not empty then the next greater
element is on top of stack*/
if (s.empty())
arr1[i] = -1;
else
arr1[i] = s.top();
s.push(arr[i]);
}
for ( int i = 0; i < n; i++)
cout << arr[i] << " ---> " << arr1[i] << endl;
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 11, 13, 21, 3 };
int n = sizeof (arr) / sizeof (arr[0]);
printNGE(arr, n);
return 0;
}
Output :
11 – 13 13 – 21 21 – -1 3 – -1
Time Complexity: O(n)
Auxiliary Space: O(n) There is no extra space required if you want to print the next greater of each element in reverse order of input(means first, for the last element and then for second last and so on till the first element)