381. Next Greater Element IV

An index needs to be beaten twice. Keep a monotonic stack of indices still waiting for their FIRST greater. When a value beats them, they've had one greater — move them to a 'pending second' collection. A min-heap (keyed by value) of pending indices lets a new value settle every pending index it now beats.

Two stages: first greater, then second

Each index must be exceeded twice. Track two groups as we sweep left to right:

• stack — indices still waiting for their first greater element (a normal monotonic decreasing stack).
• pending — indices that already found their first greater and now wait for the second. Store them in a min-heap keyed by value, so the smallest-valued waiters are checked first.

Processing value x = nums[i]

1. Settle seconds: while the heap's smallest pending value is < x, that index just got its second greater → set answer[idx] = x and pop it.
2. Promote firsts: pop from stack every index whose value < x (x is their first greater) into a temporary list, then push them all into the pending heap.
3. Push i onto stack.

Each index moves stack → pending → settled at most once, so the work is O(n log n) overall (heap operations).

Worked example

nums = [2, 4, 0, 9, 6].

• i=1 (4): 4 > 2 → index 0 promoted to pending (first greater found).
• i=3 (9): 9 > pending value 2 → answer[0] = 9 (second greater!). Also 9 > 0 and 9 > 4 → those get promoted.
• i=4 (6): 6 > pending 0 → answer[2] = 6; 6 > pending 4 → answer[1] = 6.

answer = [9, 6, 6, -1, -1].

Complexity

• Time: O(n log n) from the heap.
• Space: O(n).

class Solution {
    public int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();          // waiting for FIRST greater
        PriorityQueue<int[]> pending = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); // (value, index)
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (!pending.isEmpty() && pending.peek()[0] < x) {
                ans[pending.poll()[1]] = x;
            }
            List<Integer> tmp = new ArrayList<>();
            while (!stack.isEmpty() && nums[stack.peek()] < x) {
                tmp.add(stack.pop());
            }
            for (int idx : tmp) {
                pending.offer(new int[]{nums[idx], idx});
            }
            stack.push(i);
        }
        return ans;
    }
}