Next Greater Element

Name the variant before coding

Ask whether each element seeks the first greater value to its right in the same array, whether queries come from a subset of another array, or whether the array wraps around. For the standard right-side form, scan from right to left and maintain a strictly decreasing stack of candidates. Pop values less than or equal to the current value; the remaining top is the next greater value, or no answer exists. Push the current value.

The stack invariant is that it contains future values that have not been dominated by a closer, greater-or-equal value. Each value is pushed and popped once, giving O(n) amortized time and O(n) space, versus O(n²) brute force. For the subset variant, precompute a value-to-answer map; for a circular variant, traverse two virtual passes and only write answers in the first. Cover duplicates carefully because <= versus < determines whether equal values count as greater.