Next Greater Element in Java

Given an array, the task is to 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. If no greater element exists, consider the next greater element as -1.

Approaches:

Method 1: Naive Method

This method uses 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 the outer loop. If a greater element is found, then that element is printed as next. Otherwise, -1 is printed. The time complexity of this method is O(N^2).

Method 2: Efficient Method

This method is highly recommended to go through the solution of "Previous Greater Element in Java." If we traverse the array from the end, the problem reduces to finding the previous greater element for every element. That is, the next greater element while traversing the array from the beginning is the same as finding the previous greater element while traversing the array from the end.

To implement this method, we can use a stack to keep track of the elements. We start traversing the array from the end and push the last element to the stack. Then, we compare the top element of the stack with the current element of the array. If the top element is less than or equal to the current element, we pop the stack until we find a greater element than the current element or the stack becomes empty. If the stack becomes empty, we assign the next greater element as -1. Otherwise, we assign the top element of the stack as the next greater element. We repeat this process until we reach the beginning of the array.

To print the results from the beginning, we can keep an additional array to store answers, and print this array after finding the previous greater of every element while traversing the input array from the end.

Implementation:

java
import java.util.*;

class NextGreaterElement {

    static void printNextGreaterElement(int arr[]) {
        Deque<Integer> stack = new ArrayDeque<>();

        int n = arr.length;
        int[] res = new int[n];

        stack.push(arr[n - 1]);
        res[n - 1] = -1;

        for (int i = n - 2; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }

        for (int i = 0; i < n; i++) {
            System.out.print(res[i] + " ");
        }
    }

    public static void main(String[] args) {
        int arr[] = {4, 5, 2, 25};
        printNextGreaterElement(arr);
        // Output: 5 25 25 -1

        int arr2[] = {1, 2, 4, 8, 6, 10};
        printNextGreaterElement(arr2);
        // Output: 2 4 8 10 10 -1
    }
}

The time complexity of this method is O(N), and the auxiliary space required is O(N).

Conclusion:

In this article, we have discussed two approaches to find the next greater element for every element in an array. We have also implemented the efficient approach using a stack in Java. The efficient method has a time complexity of O(N) and is recommended for large arrays.