# 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

You must be logged in to post a comment.