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)

You may also like:
Breadth-first search (BFS) and Depth-first search (DFS) for a Graph in C++

 

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[0]); 

// 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[0]); 
printelement(arr, sn); 
return 0; 
}

Output Explanation:

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