Stack Patterns: Matching, Nesting, and More

Stacks show up in more interview problems than most people expect. On the surface, a stack is dead simple: push things on, pop things off, last in first out. But that simplicity is what makes it so versatile. Anytime you need to remember something and come back to it later, a stack is probably the right tool.

The trick is recognizing when a problem is secretly a stack problem. Once you can spot the pattern, the code almost writes itself.

Why stacks work

A stack gives you one guarantee: the last thing you added is the first thing you get back. That is LIFO, and it maps perfectly to problems involving:

• Matching pairs (every opener needs a closer, and they have to nest correctly)
• Tracking what came before (and being able to undo or revisit it)
• Processing things in reverse order (without actually reversing anything)

You do not need a special data structure. In Python, a regular list works perfectly as a stack: append() to push, pop() to remove from the end. Both are O(1).

Pattern 1: Bracket matching

This is the classic. Given a string of brackets like ({[]}), determine if every opener has a matching closer in the right order.

The insight: when you see a closing bracket, it must match the most recently opened bracket. That "most recently" part is what makes this a stack problem.

The algorithm

1. Walk through each character
2. If it is an opening bracket, push it
3. If it is a closing bracket, check the top of the stack
4. If they match, pop. If they do not match (or the stack is empty), the string is invalid
5. At the end, the stack should be empty

Step-by-step walkthrough

Here is how the algorithm processes ({[]}):

The code

def is_valid(s: str) -> bool:
    matching = {')': '(', '}': '{', ']': '['}
    stack = []

    for ch in s:
        if ch in matching:
            # Closing bracket: check top of stack
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
        else:
            # Opening bracket: push
            stack.append(ch)

    return len(stack) == 0

Notice how clean this is. The matching dictionary maps each closer to its expected opener. The stack handles the nesting for free.

Pattern 2: Monotonic stack

This one trips people up because the name sounds intimidating, but the idea is straightforward. A monotonic stack is just a stack where the elements are always in sorted order (either always increasing or always decreasing from bottom to top).

The classic problem: for each element in an array, find the next greater element to its right.

Why brute force fails

For each element, you could scan rightward until you find something bigger. That is O(n^2) in the worst case. With a monotonic stack, you do it in O(n).

The insight

Walk through the array from right to left. Maintain a stack of "candidates" for the next greater element. Before processing the current element, pop everything from the stack that is smaller or equal to it. Whatever remains on top is the answer.

Why does popping work? If a candidate is smaller than the current element, it can never be the "next greater" for anything to the left either (the current element is closer and bigger). So those candidates are useless going forward.

def next_greater_element(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices

    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater
        while stack and nums[stack[-1]] <= nums[i]:
            stack.pop()

        if stack:
            result[i] = nums[stack[-1]]

        stack.append(i)

    return result

# Example: [4, 2, 7, 1, 3]
# Result:  [7, 7, -1, 3, -1]

Variations

Monotonic stacks appear in several well-known problems:

• Daily temperatures: for each day, how many days until a warmer day? (Same pattern, store indices, answer is index difference)
• Largest rectangle in histogram: use a stack to track bar heights and calculate max area when a shorter bar appears
• Stock span: how many consecutive days was the price less than or equal to today?

The pattern is always the same: maintain sorted order on the stack by popping elements that violate it, and use what remains.

Pattern 3: State save and restore

This pattern shows up in problems where you need to process nested structures and "come back" to a previous state when you exit a level.

The classic example: evaluating or decoding nested expressions.

Decode string

Given 3[a2[bc]], produce abcbcabcbcabcbc. The brackets nest, and when you finish an inner group, you need to combine it with whatever was going on before that group started.

def decode_string(s: str) -> str:
    stack = []
    current_str = ""
    current_num = 0

    for ch in s:
        if ch.isdigit():
            current_num = current_num * 10 + int(ch)
        elif ch == '[':
            # Save current state and start fresh
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif ch == ']':
            # Restore previous state and combine
            prev_str, repeat = stack.pop()
            current_str = prev_str + current_str * repeat
        else:
            current_str += ch

    return current_str

The key idea: when you hit [, you save your current progress onto the stack. When you hit ], you pop the saved state and merge. This is the same principle behind how function calls work in any programming language, and it is the reason your computer uses a call stack.

Expression evaluation

Another common variant: evaluate "3 + 2 * 4" respecting operator precedence, or handle parenthesized expressions like "(1 + (2 * 3))".

def calculate(s: str) -> int:
    stack = []
    num = 0
    sign = 1
    result = 0

    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in '+-':
            result += sign * num
            num = 0
            sign = 1 if ch == '+' else -1
        elif ch == '(':
            # Save current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif ch == ')':
            result += sign * num
            num = 0
            result *= stack.pop()  # saved sign
            result += stack.pop()  # saved result

    result += sign * num
    return result

Common mistakes

A few things that catch people in interviews:

1. Forgetting to check if the stack is empty before popping. This is the number one bug. Always check if stack before calling stack[-1] or stack.pop().

2. Returning True too early in bracket matching. A string like (() has matching pairs along the way, but the stack is not empty at the end. You must check len(stack) == 0 after processing everything.

3. Using values instead of indices in monotonic stacks. You almost always need the index for computing distances or positions. Store the index, look up the value.

4. Not handling edge cases. Empty strings, strings with only opening brackets, single elements. Test these before submitting.

Recognizing stack problems in interviews

Here are the signals that should make you think "stack":

• The problem mentions matching or pairing (brackets, tags, delimiters)
• You need to find the next/previous greater or smaller element
• The problem involves nested structures (expressions, encoded strings, HTML)
• You need to undo or backtrack to a previous state
• The problem says "valid" and involves some kind of sequential validation

When you see these keywords, sketch out what a stack-based approach would look like before trying anything else. It is almost always the right call.

Building real fluency

Reading about stack patterns is a good start, but the gap between "I understand this" and "I can write it under pressure in 20 minutes" is bigger than most people think. The bracket matching algorithm is simple enough to memorize, but monotonic stacks and state save/restore require genuine comfort with the mechanics.

That is where spaced repetition helps. Instead of grinding 50 stack problems in a weekend and forgetting half of them by Tuesday, you practice each building block at the interval where you are about to forget it. Short sessions, spread over time, with the spacing tuned to your actual retention.

Related posts

• Hash Map Patterns - Hash maps and stacks often work together, especially in frequency-based problems with ordering constraints
• The Sliding Window Pattern - Another pattern that processes sequences in a single pass, using different state tracking
• Binary Search - Monotonic stacks and binary search both exploit sorted structure to avoid brute-force scanning

CodeBricks breaks stack problems down into the reusable pieces (the matching dictionary, the monotonic pop loop, the save/restore push) and drills them individually. You type the code from scratch each time, and the scheduling adapts to how well you remember each piece.

---

New to algorithms? Start with our visual What is an Algorithm? guide to build your foundation.