Stack Interview Questions: Patterns That Actually Matter

Stacks are one of the most versatile data structures in coding interviews. Three patterns cover the vast majority of stack problems: matching pairs (brackets, tags), monotonic stacks (next greater/smaller element), and expression parsing (postfix, infix evaluation). Master these three and you'll handle any stack question thrown at you.

When to Use a Stack

A stack is the right choice when:

• You need to match opening and closing pairs (parentheses, HTML tags, brackets)
• You need to find the next greater or smaller element for each position
• You need to evaluate mathematical expressions (postfix notation)
• The problem involves a "last in, first out" pattern (undo, backtracking)
• You're doing an iterative DFS on a tree or graph

Trigger signals: "matching pairs," "valid parentheses," "next greater," "expression," "evaluate," or "monotonic" in the problem statement.

Pattern 1: Matching Pairs (Bracket/Tag Validation)

Push opening elements onto the stack. When you see a closing element, check if it matches the top of the stack. If it matches, pop. If it doesn't match or the stack is empty, the input is invalid.

Example: Valid Parentheses

def is_valid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        else:
            stack.append(char)

    return len(stack) == 0

Walkthrough with "({[]})":

Result: True (stack is empty)

Time: O(n). Space: O(n).

Example: Min Stack (Stack with O(1) min)

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()
        return val

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.min_stack[-1]

The key insight: maintain a second stack that tracks the minimum at each level. When the current minimum is popped, the previous minimum is revealed.

Time: O(1) for all operations. Space: O(n).

Pattern 2: Monotonic Stack (Next Greater/Smaller Element)

A monotonic stack maintains elements in sorted order (either increasing or decreasing). When you encounter an element that violates the order, you pop elements from the stack and resolve their "next greater/smaller" value.

The invariant: elements in the stack are always in decreasing order (for next greater element). This means when a new element arrives, everything smaller than it gets resolved.

Example: Daily Temperatures

Given daily temperatures, find how many days you have to wait until a warmer temperature. If no warmer day exists, use 0.

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)

    return result

Walkthrough with [73,74,75,71,69,72,76,73]:

Result: [1,1,4,2,1,1,0,0]

Time: O(n) — each element is pushed and popped at most once. Space: O(n).

Example: Next Greater Element

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            result[stack.pop()] = nums[i]
        stack.append(i)

    return result

Time: O(n). Space: O(n).

Pattern 3: Expression Parsing

Stacks are the standard tool for evaluating mathematical expressions. Two common formats:

• Postfix (Reverse Polish Notation): Operators follow operands. Push numbers, apply operators to the top two elements.
• Infix to Postfix: Use the Shunting Yard algorithm with an operator stack.

Example: Evaluate Reverse Polish Notation

def eval_rpn(tokens):
    stack = []
    operators = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),
    }

    for token in tokens:
        if token in operators:
            b = stack.pop()
            a = stack.pop()
            stack.append(operators[token](a, b))
        else:
            stack.append(int(token))

    return stack[0]

Walkthrough with ["2","1","+","3","*"]:

1. Push 2 → stack = [2]
2. Push 1 → stack = [2, 1]
3. "+" → pop 1, 2 → 2 + 1 = 3 → push 3 → stack = [3]
4. Push 3 → stack = [3, 3]
5. "*" → pop 3, 3 → 3 * 3 = 9 → push 9 → stack = [9]
6. Result: 9

Time: O(n). Space: O(n).

Example: Infix to Postfix (Shunting Yard)

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    stack = []
    output = []

    for token in expression:
        if token.isdigit():
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(token, 0):
                output.append(stack.pop())
            stack.append(token)

    while stack:
        output.append(stack.pop())

    return ' '.join(output)

Walkthrough with "3 + 4 * 2":

1. "3" → output: ["3"]
2. "+" → push → stack: ["+"]
3. "4" → output: ["3", "4"]
4. "" → precedence * > +, push → stack: ["+", ""]
5. "2" → output: ["3", "4", "2"]
6. Pop remaining: output: ["3", "4", "2", "*", "+"]
7. Result: "3 4 2 * +"

Time: O(n). Space: O(n).

Complexity Summary

Common Mistakes

1. Not handling empty stack before popping. Always check if stack before stack.pop() or stack[-1]. An empty stack pop throws an error or returns unexpected values.

2. Confusing monotonic stack direction. For "next greater element," use a decreasing stack (pop when current > top). For "next smaller element," use an increasing stack (pop when current < top).

3. Forgetting that Python division truncates toward zero. In eval_rpn, use int(a / b) not a // b to match the expected behavior for negative numbers.

4. Not handling the case where no match exists. After processing all input, if the stack isn't empty (for matching pairs), the input is invalid. Always check the final stack state.

5. Using a stack when a deque is better. For sliding window maximum, a monotonic deque (double-ended queue) is more efficient than a monotonic stack. Use a stack only when you process elements left-to-right with no need to remove from the front.

Practice Problems

These problems cover the three core stack patterns. Solve them in order.

1. Valid Parentheses — The classic matching pairs pattern. Push opens, pop and verify on closes.

2. Min Stack — Design a stack that supports push, pop, top, and getMin in O(1) time.

3. Daily Temperatures — Monotonic stack. Find the number of days until a warmer temperature for each day.

4. Largest Rectangle in Histogram — Monotonic stack with width tracking. Find the largest rectangle that fits within the histogram bars.

5. Evaluate Reverse Polish Notation — Expression parsing. Evaluate a postfix expression using a stack.

Practice These Patterns With Alex

Stack problems test your ability to recognize patterns and implement them cleanly. The matching pairs pattern is straightforward, but monotonic stacks and expression parsing require careful reasoning about the stack invariant. Practice with an AI interviewer who asks you to explain your stack invariant aloud.

Start a mock coding interview →

Frequently Asked Questions