Problem

Given an array, print the Next Greater Element (NGE) for every element. The Next greater element for an element x is the first greater element on the right side of x in the array.

The elements for which no greater element exist, print -1.

Examples

Example 1:

Input:  {1, 3, 2, 4} 
Output: {3, 4, 4, -1}

Element     Next greater element on the right
1           3
3           4
2           4
4           -1

Example 2:

Input:  {6, 4, 12, 5, 2, 10} 
Output: {12, 12, -1, 10, 10, -1} 

Element     Next greater element on the right
6           12
4           12
12          -1
5           10
2           10
10          -1

Solution

Method 1 - Brute Force

The Brute force approach is to iterate over the array and for each element at index i,

  • Iterate from i+1 to n to find the next greater element.
class NearestGreaterToRight {
    private static int[] nextGreaterElement(int[] a) {
        int n = a.length;
        int[] NGR = new int[n];

        for (int i = 0; i < n; i++) {
            NGR[i] = -1;
            for(int j = i+1; j < n; j++) {
                if(a[j] > a[i]) {
                    NGR[i] = a[j];
                    break;
                }
            }
        }

        return NGR;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Monotonic Stack

Code

Java
class NearestGreaterToRight {
    public int[] nextGreaterElementUsingStack(int[] a) {
        int n = a.length;
        int[] NGR = new int[n];

        Stack<Integer> s = new Stack<Integer>();
        for(int i = n-1; i >= 0; i--) {
            NGR[i] = -1;
            while(!s.empty()) {
                int top = s.peek();
                if (top > a[i]) {
                    NGR[i] = top;
                    break;
                } else {
                    s.pop();
                }
            }
            s.push(a[i]);
        }

        return NGR;
    }
}

Complexity

  • ⏰ Time complexity: O(n). The entire array (of size n) is scanned only once. Each of the stack’s n elements are pushed and popped exactly once.
  • 🧺 Space complexity: O(n)