Java next greater element: keep unresolved indices on a stack

The top is a pending question

Each incoming value answers all smaller values at the stack top. Store indices because the output needs positions, not just values. For 4, 1, 3, 5, 2, the next greater indices are 3, 2, 3, -1, -1. An unanswered index remains -1.

The comparison is strict. Equal values do not answer each other; changing > to >= changes the task. ArrayDeque supplies the stack without the legacy Stack class. Window maximum uses a deque with a different eviction rule.

Amortized work is the point

A value can cause several pops, but each index is pushed once and popped at most once. Do not count the inner while loop as n work for every outer iteration. Input values are not modified.

Working program

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class NextGreaterReceiptLoad {
    static int[] nextGreaterIndex(int[] load) {
        int[] answer = new int[load.length];
        Arrays.fill(answer, -1);
        Deque<Integer> pending = new ArrayDeque<>();
        for (int index = 0; index < load.length; index++) {
            while (!pending.isEmpty() && load[index] > load[pending.peek()])
                answer[pending.pop()] = index;
            pending.push(index);
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreaterIndex(new int[]{4, 1, 3, 5, 2})));
        if (nextGreaterIndex(new int[]{2, 2})[0] != -1) throw new AssertionError("strict comparison");
    }
}

Output

[3, 2, 3, -1, -1]

Costs and boundaries

The scan takes O(n) time and O(n) worst-case stack and answer space. Each index has at most one push and one pop, despite the nested while loop.

Common Mistakes

• Do not replace > with >= unless equal values should count.
• Do not store only values when the answer needs an index.
• Do not claim the while loop makes this quadratic.

Read next

Java ArrayDeque for queues and stacks, Java sliding windows: fixed-size range totals, Java stack algorithm: validate nested delimiters.