For each element of an array, find the first element to its right that is larger. State the invariant your stack maintains.

The invariant, stated before any code

The stack holds the indices of elements whose next greater element has not been found yet, and their values are strictly decreasing from the bottom of the stack to the top.

That single sentence generates the algorithm. If the values on the stack are decreasing, then when a new element arrives it is greater than a contiguous run at the top and the moment it stops being greater it cannot be greater than anything deeper, so popping can halt immediately. And because the popped elements are being resolved by the first larger element to arrive after them, the value being popped against is by construction the nearest one to the right, which is what the problem asks for.

Candidates who write the loop first and reason afterwards usually produce something that works on the example in the problem statement and fails on a plateau of equal values. Candidates who state the invariant get the comparison operator right on the first attempt, because the operator is a direct consequence of the word "strictly".

The scan

int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);                                  // default: nothing larger to the right

    Deque<Integer> stack = new ArrayDeque<>();             // indices, values strictly decreasing
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            res[stack.pop()] = nums[i];                    // nums[i] is the nearest larger for this index
        }
        stack.push(i);
    }
    return res;                                            // whatever is still on the stack keeps -1
}

The stack stores indices, not values, because the resolved answer has to be written into a specific output slot. Storing values forces a second structure to remember where they came from, which is a tell that the invariant was never articulated.

Prefilling the result with -1 handles the tail of the array without a cleanup pass. Everything still on the stack when the scan ends is exactly the set of indices with no larger element to their right - the suffix maxima - and they keep the default. An explicit drain loop that writes -1 again is harmless but redundant, and being able to say why it is redundant is the better answer.

Use ArrayDeque rather than the legacy java.util.Stack, which extends Vector and synchronises every operation for no benefit here. Note that ArrayDeque rejects null elements, which is a non-issue for boxed indices and occasionally a surprise elsewhere.

Defending the linear bound

The code contains a while inside a for, so an interviewer will ask whether it is quadratic. It is not, and the argument has to be about the stack rather than about the loops.

Each index is pushed exactly once, by the iteration that reaches it. Each index can be popped at most once, because once popped it is never re-pushed. So across the entire run the inner while body executes at most n times in total, no matter how it clusters. A strictly decreasing input never pops until the end and a strictly increasing input pops once per step, and both come to the same total.

This is an amortised argument, and it is worth naming it as such. Any single iteration can cost O(n) - the arrival of a new maximum after a long descent clears the whole stack - so the per-element bound is not O(1). The total is O(n) time and O(n) space for the stack in the worst case, which is the input already sorted descending.

Where the plateau breaks the answer

Equal values are the case interviewers reach for, and < versus <= in the comparison is the whole of it. With nums[stack.peek()] < nums[i] an equal element does not pop, so a duplicate is left waiting for something strictly larger, which is the correct behaviour for "next greater". Switching to <= makes an equal element resolve the earlier one, answering "next greater or equal" instead. Neither is wrong in the abstract; being unable to say which one your code implements is.

The related slip is a plateau at the end of the array. On [2, 2, 2] the strict version leaves all three indices on the stack and returns three -1 values, which is right. A candidate who tested only on strictly increasing input will not have noticed that their stack can grow to the full array length, and their space estimate will be wrong along with their tie-breaking.

The invariant is the deliverable, not the code. Every problem in this family - daily temperatures, largest rectangle in a histogram, trapping rain water - is the same fifteen lines with a different ordering predicate, so the reusable skill is being able to write the invariant down and derive the comparison from it.