Next Greater Element

Method 2 - Using stack

The other way to program is by using a stack data structure. First, push only the first element from the array to the stack. Then pick left-out elements of the array one by one and follow the steps in the loop.

• Mark current element as nge.
• Compare the top element of the stack if not empty with nge.
• If the top element is less than nge, then pop element from the stack. Popped element will have the next greater element in nge.
• Keep following the above step while the popped element is smaller than nge. Nge will be the next greater element for all those elements.

After that, push the nge element in the stack. After the loop is finished, pop each element and print -1 as their next greater element for them.

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

void nextGreaterEle(int numArr[])
{
    stack<int> st;
    st.push(numArr[0]);
    for (int i = 1; i < 5; i++)
    {
        if (st.empty()) {
            st.push(numArr[i]);
            continue;
        }

        while (st.empty() == false && st.top() < numArr[i])
        {
            cout << st.top()<< " -> " << numArr[i] << endl;
            st.pop();
        }

        st.push(numArr[i]);
    }
 
    while (st.empty() == false) {
        cout << st.top() << " -> " << -1 << endl;
        st.pop();
    }
}
 
/* Driver code */
int main()
{
    int arr[] = {5, 10, 4, 12, 2};
    nextGreaterEle(arr);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

5 -> 10
10 -> 12
4 -> 12
12 -> -1
2 -> -1

You can also try this code with Online C++ Compiler

Run Code

The time complexity of the above code is O(n) and space complexity is also O(n).

The worst case of the above program will occur when all elements are present in decreasing order. In this case, each element will be processed at most four times. This program may also print the output in a different order.

So, to reduce complexity and get the output in the same order, we can traverse from behind, i.e., in reverse order. Implementation of this is shown below through codes.

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

void nextGreaterEle(int numArr[])
{
    stack<int> s;
    int res[5];
    for (int i = 4; i >= 0; i--) {

        if (!s.empty()) {
            while (!s.empty() && s.top() <= numArr[i]) {
                s.pop();
            }
        }
        res[i] = s.empty() ? -1 : s.top();
        s.push(numArr[i]);
    }
    for (int i = 0; i < 5; i++)
        cout << numArr[i] << " -> " << res[i] << endl;
}
// Driver Code
int main()
{
    int arr[] = {5, 10, 4, 12, 2};
    nextGreaterEle(arr); // Function call
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

5 -> 10
10 -> 12
4 -> 12
12 -> -1
2 -> -1

You can also try this code with Online C++ Compiler

Run Code

Time and space complexity will be the same, i.e., O(n).

Try and compile by yourself with the help of online C++ Compiler for better understanding.

Also read -  Decimal to Binary c++

FAQs

1. Which data structure is used to find the next greater element with an array?
   Stack is used with the array in the program.
    
2. What are the different functions used that are related to the stack?
   push(), pop(), empty() and top() are the inbuilt functions of stack that are used in the program.
    
3. How can we find the size of the array in the program?
   The size of an array can be calculated with the help of the sizeof() function.
   Size = sizeof(arr) / sizeof(arr[0]) will be used.

Key Takeaways

In this article, we have extensively discussed how to find the next greater element and its implementation in C++. The blog contains different ways by which we can find the next greater element with their time complexity and space complexity.

Check out this problem - Next Smaller Element

We hope that this blog has helped you enhance your knowledge of finding the next greater element. Do upvote our blog to help other ninjas grow. Happy Coding!