Stacks & monotonic stacks

Remember data in a Last-In, First-Out (LIFO) order to process immediate dependencies.

The idea

A standard Stack is like a stack of plates: you can only add to the top (push) and remove from the top (pop). This LIFO property is perfect for matching parentheses or undoing operations.

A Monotonic Stack is a powerful variation. We enforce a rule: the elements in the stack must stay strictly increasing (or strictly decreasing). When a new element arrives, we pop elements off the stack until the rule is satisfied again. This is exactly how you solve "find the Next Greater Element" in O(n) time instead of O(n²).

Array (scanning L to R)

Stack (indices)

Target: Find the Next Greater Element for each item.

How it works

By keeping a stack of unresolved indices (elements waiting for a greater element), we ensure each item is pushed once and popped once, giving O(n) total time.

def next_greater_elements(nums):
    res = [-1] * len(nums)
    stack = []  # Stores indices
    
    for i in range(len(nums)):
        # While stack is not empty and current element > element at stack top
        while stack and nums[i] > nums[stack[-1]]:
            popped_idx = stack.pop()
            res[popped_idx] = nums[i]
            
        stack.append(i)
        
    return res

Cost

Time Complexity O(N)

Space Complexity O(N)

Even with a nested while loop, every element is pushed to the stack exactly once and popped at most once. 2N operations = O(N) time.

Watch out for

Stacking values vs indices: It is almost always better to store the index of the element in the stack, rather than the value itself. With the index, you can easily look up the value and know exactly where to put the result in your answer array.
Decreasing vs Increasing: If you want the "next greater element", you use a monotonically decreasing stack (you pop when you find a larger element). If you want the "next smaller element", you use a monotonically increasing stack.