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

 

Leave a Reply

Your email address will not be published. Required fields are marked *