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