Next Greater Element to the Right

Maintain useful future candidates

Scan from the final element toward the first. Before answering a[i], pop stack values that are less than or equal to a[i]: they cannot be a next greater answer for a[i], and they are also blocked by a[i] for every position further left. The remaining top is the nearest greater value to the right; if the stack is empty, return -1 or the specified sentinel. Push a[i].

The invariant is that the stack holds a decreasing sequence of still-visible candidates from the suffix. Although there is a nested loop, every value enters once and leaves once, so runtime is O(n) and space is O(n). Test strictly increasing input, strictly decreasing input, duplicate values, a single element, and negative values. If the problem asks for indices instead of values, store indices and compare through the array. State whether equal values count as greater; standard next-greater semantics require strictly greater values.