Next Greater Element in Linear Time in JAVA

This is my implementation of the algorithm for that gets the next greater element than the current element in linear time. For elements with no next greater element, match it with a -1.

Setup

# Given an array [4, 3, 5, 2, 1, 8, 20, 17]
# Print out the follow:
# (3, 5), (4, 5), (1, 8), (2, 8), (5, 8), (8, 20), (17, -1), (20, -1)

The brute force solution would be to have a loop that loops through all the elements, and compare all the elements downstream from the current element per iteration to see if it is greater. The time complexity of this is O(n^2).

Time & Space

The optimized solution takes advantage of the stack data structure. It is a placeholder for all numbers that have not been matched with a greater element in hope of encountering with one downstream during the iteration. This algorithm has O(n) time and space complexities. The code below is the implementation of the algorithm.

public static void printNextGreatterElement(int[] arr) {
    int n = arr.length;
    if (n == 0) return;

    Stack<Integer> orphans = new Stack<Integer>();
    orphans.push(arr[0]);

    for (int i = 1; i < n; i++) {
        int cur = arr[i];

        while (!orphans.isEmpty() && orphans.peek() < cur) {
            System.out.printf("(%d, %d) ", orphans.pop(), cur);
        }

        orphans.push(cur);
    }

    while (!orphans.isEmpty()) {
        System.out.printf("(%d, -1) ", orphans.pop());
    }
}

This article is my 18th oldest. It is 230 words long, and it’s got 0 comments for now.