Stacks

A stack is one of the simplest data structures you'll ever implement, and yet it quietly powers some of the most elegant algorithms in interview prep: push, pop, and peek, all at one end, all in O(1). That "last in, first out" (LIFO) discipline turns out to be exactly the right tool whenever a problem has nested or matching structure, or whenever you need to "remember what came before until something later resolves it."

Think about a string of parentheses. When you see a closing bracket, the thing it must match is not just "any" earlier open bracket — it's the most recently opened, still-unclosed one. That's precisely what a stack gives you for free: push every opening bracket, and when a closing bracket arrives, pop and check it against the top. If the stack empties out cleanly by the end, the string was balanced. The same idea generalizes to evaluating arithmetic expressions, where operators wait on a stack until their operands are ready, and to Reverse Polish Notation, where operands themselves sit on a stack until an operator consumes the two most recent ones.

Stacks also show up in problems that have nothing to do with brackets on the surface. Repeatedly canceling adjacent duplicate characters in a string, or simulating a FIFO queue using only stack primitives, both lean on the same "remember the recent past, resolve it later" instinct.

The monotonic stack

A second, more subtle pattern is the monotonic stack: a stack whose elements are kept in strictly increasing or strictly decreasing order from bottom to top. It's the standard tool for "next greater element," "next smaller element," and similar problems where, for every item, you want to know the nearest neighbor (to the left or right) that breaks some inequality.

The trick is that instead of comparing every pair of elements (O(n^2)), you scan once and let the stack do the filtering. As you scan left to right looking for the next greater element, you push indices onto the stack while their values are increasing. The moment you see a value bigger than the stack's top, that new value is the "next greater" answer for everything on the stack that's smaller than it — so you pop them all, record the answer, and keep going. Every element is pushed exactly once and popped at most once, so the whole scan is O(n) even though it looks like it might involve nested loops.

A generic template looks like this:

stack = []  # holds indices, kept monotonic by value
for i, value in enumerate(array):
    while stack and array[stack[-1]] < value:
        j = stack.pop()
        result[j] = value       # value is the "next greater" for index j
    stack.append(i)
# anything left on the stack has no next-greater element

The sliding-window maximum problem extends this same idea to a monotonic deque: a double-ended queue kept in decreasing order, where you can pop from the back (to maintain monotonicity as new elements arrive) and pop from the front (to evict elements that have slid out of the window). The front of the deque is always the maximum of the current window.

Complexity and pitfalls

Both plain and monotonic stack techniques are typically O(n) time and O(n) space: every element enters and leaves the stack (or deque) a constant number of times. The most common mistakes are: popping in the wrong direction (e.g., building an increasing stack when you need decreasing, or vice versa), forgetting that whatever is left on the stack at the end usually represents "no answer found" and needs explicit handling, and reaching for a stack when the problem actually needs FIFO order — that's a sign you need a queue or a deque instead.