Stack: Next Greater Element

Problem Statement:

you are given an array, you need to get the next greater element for every element in the array.

The next greater element for an element is the first greater element on the right side of x in the array.

If there is no greater element then mark it as -1.

Example

Element        Next Greater Element
   5      -->   6
   6      -->   28
   7      -->   28
   28     -->   -1

Solution

We can solve this by using stacks.

Push first element into the stack.

Take the next element and make it as “next”

If the stack is not empty compare the top element of the stack with next.

If next is greater than the top element pop element from stack. The next is the greater element for the popped element.

Keep popping from stack while the popped element is smaller than the next.

Finally push the next in the stack.

Example:

Array: 11, 13, 21, 3
Stack: 11
i = 1

Pass 1: 

arr[i] > s.top
s.pop()
Hence next greater element of 11 is 13.
s.push(arr[i])

Array: 11, 13, 21, 3
Stack: 13
i = 2

Pass 2: 

arr[i] > s.top
s.pop()
Hence next greater element of 13 is 21.
s.push(arr[i])

Array: 11, 13, 21, 3
Stack: 21
i = 3

Pass 3: 

arr[i] < s.top
s.push(arr[i])

Array: 11, 13, 21, 3
Stack: 21, 3
reached end of array

Pass 4:

Hence next greater element for 3 is -1
s.pop()

Pass 5:
Hence next greater element for 21 is -1
s.pop()

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;

void print_next_greater_element(int arr[], int n)
{
    stack<int> s;
 
    s.push(arr[0]);
 
    for (int i = 1; i < n; i++) 
    {
 
        if (s.empty()) 
        {
            s.push(arr[i]);
            continue;
        }
 
        while (s.empty() == false && s.top() < arr[i]) 
        {
            cout <<"Next greater element of "<< s.top() 
                 << " is " << arr[i] << endl;
            s.pop();
        }
 
        s.push(arr[i]);
    }

    while (s.empty() == false) 
    {
        cout << "Next greater element of "<<s.top() << " is " << -1 << endl;
        s.pop();
    }
}
 
int main()
{
    int arr[] = { 12, 14, 22, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    print_next_greater_element(arr, n);
    return 0;
}

Output:

Next greater element of 12 is 14
Next greater element of 14 is 22
Next greater element of 4 is -1
Next greater element of 22 is -1