Program to find Next Greater Element

Given: An array, we have to print the next greater element for each element. The Next greater Element for an element p is the first greater element on the right side of p in array. Elements for which there is no greater element, we consider next greater element as -1.  

Example:

Input array: { 37, 23, 64, 10, 25, 7 }
Output:
Next greater element for 37     = 64
Next greater element for 23     = 25
Next greater element for 64     = -1
Next greater element for 10     = 23
Next greater element for 25     = 37
Next greater element for  7      = 10

# Brute Force Approach 

Code:

#include <iostream>

// prints NGE for all elements of array[]  
void nextgren(int array[], int size)
{
    int next;
    for (int i = 0; i < size; i++)
    {
        next = -1;
        for (int j = i + 1; j < size; j++)
        {
            if (array[i] < array[j])
            {
                next = array[j];
                break;
            }
        }
        std::cout << "Next greater element for " << array[i] << " = " << next << std::endl;
    }
}

// Driver Code
int main()
{
    int array[] = { 5, 4, 7, 15 };
    int size = sizeof(array) / sizeof(array[0]);
    nextgren(array, size);
    return 0;
}

Output

Next greater element for 5 = 7
Next greater element for 4 = 7
Next greater element for 7 = 15
Next greater element for 15 = -1

Time Complexity: O(n2).

# Optimised Approach(Using Stack)

Code:

// C++ program to find next greater element using stack
#include <bits/stdc++.h>

// prints NGE for all elements of array
void nextgren(int array[], int size)
{
    std::stack<int> stck;
    // push first element to stck 
    stck.push(array[0]);
    // iterating for next elements
    for (int i = 1; i < size; i++)
    {
        if (stck.empty())
        {
            stck.push(array[i]);
            continue;
        }
        /*if stck is not empty, then pop an element from stck.
        If the popped element is smaller than next, then
        1) print the element and next
        2) keep popping while elements are smaller and stck is not empty */
        while ((stck.empty() == false) && (stck.top() < array[i]))
        {
            std::cout << "Next greater element for " << stck.top() << " = " << array[i] << std::endl;
            stck.pop();
        }
        // push next to stck so we can find next greater for it
        stck.push(array[i]);
    }
    /*After iteration is over, the remaining
    elements in stck do not have the next greater
    element, so we print -1 for them */
    while (stck.empty() == false)
    {
        std::cout << stck.top() << " --> " << -1 << " (No greater element in given input) " << std::endl;
        stck.pop();
    }
}

// Driver code
int main()
{
    int array[] = { 6, 10, 12, 9 };
    int size = sizeof(array) / sizeof(array[0]);
    nextgren(array, size);
    return 0;
}

Output

Next greater element for 6 = 10
Next greater element for 10 = 12
12 --> -1 (No greater element in given input) 
9 --> -1 (No greater element in given input) 

Time Complexity: O(n).