Next greater element

Print Next Greater Element for every element in the array. The Next greater Element of element x is first greater element on its right side.
Elements for which no greater element exist, next greater element is -1.

Example:
- For any array, rightmost element always has next greater element as -1.
- All elements of an array sorted in decreasing order have next greater element as -1.
- For input array {5, 9, 1, 15}, the next greater elements of each element are as follows.
{9, 15, 15, -1}
- For input array {20, 17, 15, 10}, the next greater elements are {-1, -1, -1, -1}

Method-1: Brute-Force
Use two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by outer loop. If a greater element is found then that element is printed as next, otherwise -1 is printed.
This method takes O(n²) time in worst case
Method-2: Using Stack
The algorithm is as follows

1. Push first element into stack.
2. Pick other elements one by one and follow .
   a) Mark current element as next.
   b) If stack is not empty, pop element from stack and compare it with next.
   c) If next is greater than popped element, then next is the next greater element for the popped element.
   d) Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
   g) If next is smaller than the popped element, then push the popped element back.
3. After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

void printNGE(int *arr, int n)
{
    int i = 0;
    Stack s;
    int element, next;
    // PUSH FIRST ELEMENT
    push(&s, arr[0]);
    // TRAVERSE OTHER ELEMENTS
    for (i=1; i<n; i++)
    {
        next = arr[i];
        if (s.isEmpty() == false)
        {
            // IF STACK NOT EMPTY, POP
            element = s.pop();
            /* If the popped element < next, then
                 - print pair
                 - keep popping till elements are smaller and stack is not empty */
            while (element < next) { printf("\n %d --> %d", element, next);
                if(s.isEmpty() == true)
                   break;
                element = s.pop();
            }
            /* If element is > next*/
            if (element > next)
                s.push(element);
        }
        s.push(next);
    }
    // REMAINING ELEMENTS
    while (!s.isEmpty())
    {
        element = s.pop();
        next = -1;
        printf("\n %d -- %d", element, next);
    }
}

Above method takes O(n) time.