Print the next greater element in C++

In this tutorial, we will learn how to print the next greater element C++. Then, we have an array and we have to print the next greater element of each element.

For Example :

• Given array: {1, 4, 0, -1, 5, 2}
• If there is no greater element in the right, then print -1.
• For the rightmost element, print -1.
• This is how we can find the output of this problem.
• Output: 1 –> 4
4 –> 5
0 –> 5
-1 –> 5
5 –> -1
2 –> -1
• Given array: { 13, 45, 12, 9}
•  Then, output:
13 –> 45
45 –> -1
12 –> -1
9 — > -1

Moreover, we can solve this problem by these two methods.

Simple Method:

• Using two for loops.
• The outer loop will traverse through element one by one.
• Then, the inner loop will find the greatest element in the rest of the element

Therefore, we will use the stack to solve.

Method using stack:

• Firstly, push the first element to the stack.
• Then, pick the remaining elements from the stack and apply the following steps.
• We have to mark the current element as next
• Now, check for the stack if it is empty or not. If it is not empty, then compare the top element of the stack with the next.
• If next is greater than the top element of the stack, then Pop the element from the stack.
• Now, next is the next greater element for the popped element of the stack.
• We have to keep popping elements from the stack while the popped element becomes smaller than the next element.
• Again,  next becomes the next greater element for all popped element of the stack.
• Now we have to push the next in the stack.
• Then, the time complexity: O(n)

C++ program to print the next greater element

Implementation:

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

// print element function
void printelement(int arr[], int sn) {
stack < int > st;

/* push  first element */
st.push(arr);

// iterate for remaining
for (int i = 1; i < sn; i++) {

if (st.empty()) {
st.push(arr[i]);
continue;
}
//check the above conditions here
while (st.empty() == false && st.top() < arr[i])
{
cout << st.top() << " --> " << arr[i] << endl;
st.pop();
}

// push next element to stack
st.push(arr[i]);
}

//if it is not empty
while (st.empty() == false) {
cout << st.top() << " --> " << -1 << endl;
st.pop();
}
}

int main() {
int arr[] = { 13,45,12,9};
int sn = sizeof(arr) / sizeof(arr);
printelement(arr, sn);
return 0;
}

Output Explanation:

INPUT: { 13,45,12,9}
OUTPUT: 13 --> 45
9 --> -1
12 --> -1
45 --> -1