A stack that stays sorted (increasing or decreasing) so the next greater/smaller element for each item can be popped in one pass. O(N).

Data Flow (next greater to the right)

arr = [2, 1, 2, 4, 3]

i=0 (2) -> stack empty -> push 0
i=1 (1) -> push 1
i=2 (2) -> 2 > 1 pop 1 result[1]=2; push 2
i=3 (4) -> 4 > 2 pop result[2]=4; 4 > 2 pop result[0]=4; push 3
i=4 (3) -> push 4

result: [-1, 2, 4, -1, -1]

When to use

• “Next greater / smaller element” (left or right).
• “Daily temperatures”.
• Largest rectangle in histogram.

Code (next greater to the right)

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            j = stack.pop()
            res[j] = n
        stack.append(i)
    return res

Pitfalls

• Forgetting to push a placeholder 0 at the end (drains the stack).
• Off-by-one on width = i - stack[-1] - 1 when the stack is non-empty.

Analogy

A row of buildings; for each, find the next taller building to its right. Use the stack of “still waiting” buildings.

Interview tip: If the prompt says “for each element, find something to the left/right”, think stack. If “monotonic” or “non-overlapping”, think monotonic stack.