The pattern

Push indices onto a stack while their values are strictly increasing (or strictly decreasing, depending on the problem). When you see a value that breaks the invariant, pop until it doesn’t.

What you pop represents an element whose “next greater” (or “next smaller”) has finally been found — the current element.

Template

def next_greater(nums):
    n = len(nums)
    answer = [-1] * n
    stack = []  # holds indices, values decreasing top→bottom

    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            j = stack.pop()
            answer[j] = x
        stack.append(i)

    return answer

Time: O(n). Each index is pushed and popped at most once. Space: O(n) for the stack and output.

When this pattern shows up

• Next greater / smaller element — direct
• Daily temperatures — same problem, framed as days-to-wait
• Largest rectangle in histogram — pop while current bar < top of stack
• Sum of subarray minimums — count how many subarrays each element is the min of
• Trapping rain water — variant where we track both sides

What I keep getting wrong

• Strict vs non-strict — < vs <= matters when there are duplicates. For “next strictly greater,” use <. For “next greater or equal,” use <=.
• Storing values vs indices — when the answer depends on distance (e.g., daily temperatures), you must store indices.
• Direction — sometimes scanning right-to-left is cleaner. The stack is the same, just the loop direction flips.

Problems to try