Monotonic stack

1
2
3
4
5
6
7
8
9
10
11
12

Goal: Find next greater element to the right for each number.

Scan from Right to Left (index 4 -> 3 -> 2 -> 1 -> 0):
1. Element 3 (idx 4): Stack is empty -> NGE is -1. Push 3.           Stack: [ 3 ]
2. Element 4 (idx 3): Top 3 is smaller -> Pop 3. Stack empty -> -1. Push 4. Stack: [ 4 ]
3. Element 2 (idx 2): Top 4 is greater -> NGE is 4. Push 2.           Stack: [ 4, 2 ]
4. Element 1 (idx 1): Top 2 is greater -> NGE is 2. Push 1.           Stack: [ 4, 2, 1 ]
5. Element 2 (idx 0): Top 1 is <= 2 -> Pop 1. Top 2 is <= 2 -> Pop 2.
                      Top 4 is greater -> NGE is 4. Push 2.           Stack: [ 4, 2 ]

Final Output: [4, 2, 4, -1, -1]
Total Time: Every element is pushed once and popped at most once = O(n) linear time!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // stores values (or indices)

    for (int i = n - 1; i >= 0; i--) {
        // Pop all elements that are smaller than or equal to current number
        while (!stack.isEmpty() && stack.peek() <= nums[i]) {
            stack.pop();
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}