Top 12 Stack Interview Problems: Every Pattern You'll See

A stack is just an array with trust issues about the middle. Naturally, interviewers love it.

Six patterns. One data structure. Every stack problem in a software engineering interview belongs to exactly one of them. The catch is that you need to name the pattern before you touch code, and that's the part most people skip entirely.

Most candidates grind random stack problems and hope pattern recognition emerges on its own. It doesn't, not in 45 minutes under pressure. This guide orders twelve problems by pattern so you build the framework first and the problem count second. Each entry covers the key insight, the critical code, and the mistake that actually gets people rejected.

The Six Families (Name Yours Before You Code)

Pattern	Signal in the problem	Representative problem
Push-pop matching	Paired delimiters, open/close tokens	Valid Parentheses
Auxiliary tracking	O(1) query on min/max of live stack	Min Stack
Operand evaluation	Postfix or infix expression with operators	Evaluate RPN
Monotonic stack	"Next greater/smaller," spans, or area	Daily Temperatures
Simulation	New element may eliminate multiple previous ones	Asteroid Collision
Greedy + monotonic	Smallest or largest digit sequence under constraints	Remove K Digits

Identifying which pattern a problem uses is the first move. Everything else is mechanics.

Foundation (Easy to Medium)

1. Valid Parentheses (LC 20)

Pattern: push-pop matching.

Opening brackets go on the stack. Each closing bracket either matches the top or the string is invalid. The only real decision is what to check when you see a closing bracket. That's the whole problem.

def isValid(s: str) -> bool:
    stack = []
    match = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in match:
            if not stack or stack[-1] != match[c]:
                return False
            stack.pop()
        else:
            stack.append(c)
    return not stack

The common mistake: comparing the closing bracket to itself (stack[-1] == c) instead of looking up the matching opener. Also forgetting return not stack. An unmatched ( at the end is invalid, and the function would silently return True. Both bugs have ended real interviews.

2. Min Stack (LC 155)

Pattern: auxiliary tracking.

A single stack can't answer getMin() in O(1) once you start popping. You might think "I'll just scan the stack to find it." You will be wrong, because O(n) is not O(1). The fix is a parallel stack that stores the current minimum at every level.

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        min_val = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(min_val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def getMin(self) -> int:
        return self.min_stack[-1]

When you pop, the minimum reverts automatically because you pop both stacks in lockstep. No recomputation, no drama.

3. Evaluate Reverse Polish Notation (LC 150)

Pattern: operand evaluation.

Operands go on the stack. Operators pop two, compute, push the result. The structure is clean. The trap is integer division: it must truncate toward zero, not floor like Python's //.

int(-7 / 2) gives -3. (-7) // 2 gives -4. One of these is what the problem wants. The other gets you a wrong answer with no obvious error message.

def evalRPN(tokens: list[str]) -> int:
    stack = []
    ops = {'+': lambda a, b: a + b, '-': lambda a, b: a - b,
           '*': lambda a, b: a * b, '/': lambda a, b: int(a / b)}
    for t in tokens:
        if t in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(ops[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

Pop order matters: b comes off first but a op b is the correct operand order. Get this backwards and your subtraction tests will lie to you.

Me writing clean code at home vs. the moment they say 'let's share screens'

At home you're a cop. In the interview you're Doofus. The gap is always the patterns you skipped.

Core Patterns (Medium)

4. Daily Temperatures (LC 739)

Pattern: monotonic stack, first exposure.

For each day, find how many days until a warmer temperature. Brute force is O(n²). A monotonic stack of indices gets it to O(n).

Think of the stack as a waiting room. Each temperature index takes a number and sits down. When something warmer shows up, everyone who was colder wakes up, records the wait time, and leaves. The pop is where the answer gets written, not the push. This mental model transfers to every monotonic stack problem you'll ever see.

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    result = [0] * len(temperatures)
    stack = []  # decreasing order of temperatures, stores indices
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

Push on the way in, answer on the way out. O(n) total because each index enters and leaves exactly once.

5. Next Greater Element II (LC 503)

Pattern: circular monotonic stack.

Same waiting room as LC 739, but the array wraps around. Someone near the end might have to wait past index 0. Loop twice over indices 0 to 2n-1, but only push indices from the first n iterations.

def nextGreaterElements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    return result

The if i < n guard prevents pushing the same index twice on the second pass. Without it you'd add each index twice and the cleanup never happens.

6. Decode String (LC 394)

Pattern: nested structure.

"3[a2[bc]]" becomes "abcbcabcbcabcbc". Brackets nest, so each [ introduces a new scope. Push the current string and multiplier onto the stack when you see [. Pop and reconstruct on ].

def decodeString(s: str) -> str:
    stack = []
    current_str, current_num = "", 0
    for c in s:
        if c.isdigit():
            current_num = current_num * 10 + int(c)
        elif c == '[':
            stack.append((current_str, current_num))
            current_str, current_num = "", 0
        elif c == ']':
            prev_str, num = stack.pop()
            current_str = prev_str + num * current_str
        else:
            current_str += c
    return current_str

Multi-digit numbers are why you multiply by 10 before adding. Forgetting this breaks any number above 9, which is a subtle bug that passes half the test cases.

7. Asteroid Collision (LC 735)

Pattern: simulation.

Positive asteroids move right, negative move left. They only collide when a positive is followed by a negative. A single incoming asteroid may destroy multiple stack elements, get destroyed itself, or pass through entirely. The while/break/else structure handles all three outcomes cleanly, which is the whole challenge.

def asteroidCollision(asteroids: list[int]) -> list[int]:
    stack = []
    for a in asteroids:
        while stack and a < 0 and stack[-1] > 0:
            if stack[-1] < -a:
                stack.pop()
                continue
            elif stack[-1] == -a:
                stack.pop()
            break
        else:
            stack.append(a)
    return stack

The else on the while runs when the loop exits without a break, meaning the asteroid survived all collisions and gets pushed. Python's for/while else confuses people in calm settings. In an interview it's a gift.

8. Car Fleet (LC 853)

Pattern: sort then monotonic stack.

Sort cars by position descending. Compute time-to-target for each. If a trailing car arrives no later than the car ahead, it merges into a fleet. Think of arrival times as heights: push when strictly greater, skip when less than or equal.

def carFleet(target: int, position: list[int], speed: list[int]) -> int:
    pairs = sorted(zip(position, speed), reverse=True)
    stack = []
    for pos, spd in pairs:
        time = (target - pos) / spd
        if not stack or time > stack[-1]:
            stack.append(time)
    return len(stack)

Stack length equals fleet count. The sort is not optional: processing front-to-back is what makes the merge condition correct. Process back-to-front and you're comparing a car to one it can never catch.

9. Remove K Digits (LC 402)

Pattern: greedy + monotonic stack.

Remove k digits to get the smallest possible number. The insight is that a large digit appearing before a small digit is always bad. Greedily pop the stack whenever a digit is larger than the incoming one and you still have removals left. This ensures no larger digit ever sits in front of a smaller one.

def removeKdigits(num: str, k: int) -> str:
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    if k:
        stack = stack[:-k]
    return ''.join(stack).lstrip('0') or '0'

If k is still positive after the loop, remove from the right. Those are the largest remaining digits with nowhere left to be beaten. The lstrip and or '0' handle leading zeros and the empty-result edge case. Skip either one and you'll fail examples you'd never think to try.

Hard Tier (Where Interviewers Separate People)

10. Largest Rectangle in Histogram (LC 84)

The canonical hard monotonic stack problem. For each bar, the rectangle it can form extends left and right until a shorter bar blocks it. A monotonic stack of indices tracks exactly where those walls are.

When you pop a bar, the current index is its right boundary. The new stack top is its left boundary.

def largestRectangleArea(heights: list[int]) -> int:
    stack = []  # increasing heights, stores indices
    max_area = 0
    heights.append(0)  # sentinel flushes all remaining bars
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

The sentinel 0 at the end forces every remaining bar to be popped and measured. Without it, bars that never encounter a shorter right neighbor get skipped entirely. The sentinel is not optional; it's the reason the loop is clean.

11. Longest Valid Parentheses (LC 32)

This is where LC 20's pattern gets genuinely hard. Counting pairs is easy. Knowing where a valid sequence starts and ends when the sequence might restart mid-string is not.

Store indices in the stack. Push -1 as a base. When you hit an unmatched ), push its index as the new base for future lengths.

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    max_len = 0
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # new base
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

i - stack[-1] gives the length of the valid substring ending at i. The base index is always the index just before the current valid run started. The -1 initialization handles the case where the string begins with a valid sequence.

12. Basic Calculator (LC 224)

Parentheses mean nested evaluation. You can't evaluate ahead, so you save state when entering a paren and restore it when leaving.

Push (current_result, current_sign) on open paren. Pop and combine with the inner result on close paren.

def calculate(s: str) -> int:
    stack = []
    result, num, sign = 0, 0, 1
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':
            stack.append((result, sign))
            result, sign = 0, 1
        elif c == ')':
            result += sign * num
            num = 0
            prev_result, prev_sign = stack.pop()
            result = prev_result + prev_sign * result
    return result + sign * num

The final result + sign * num handles expressions that end with a number rather than an operator. Missing it fails on inputs like "2+3". It looks like you've covered everything, right up until you haven't.

Stack Problem Frequency by Tier

Tier	Problems	When they appear
Must-know	LC 20, 155, 739	Any company, any level
Very common	LC 150, 503, 394, 735	Phone screens and onsite
Medium-hard	LC 853, 402	Onsite rounds
Hard	LC 84, 32, 224	Senior and hard-tier rounds

What to Take Away

Identification first. Every stack problem maps to one of six patterns. Spend the first two minutes naming the pattern before touching code. This alone separates people who look confident from people who look lost.

Monotonic stack is the most frequent non-obvious pattern. Master it on LC 739. LC 503 and LC 84 will feel like variations, because they are. The waiting-room mental model carries.

Simulation problems (LC 735, LC 853) don't announce themselves as stack problems. The signal: a new element can annihilate or absorb multiple previous elements in sequence.

Greedy + monotonic (LC 402) generalizes. Any "produce the smallest or largest sequence under a budget" problem likely uses this shape.

LC 20 through LC 32 is a three-difficulty arc. Valid Parentheses teaches the push-pop reflex. Longest Valid Parentheses shows how painful that reflex becomes once you need to track lengths instead of existence.

LC 224 is the ceiling for standard interviews. Push and pop evaluation state on nested scopes. That pattern generalizes to any grammar with paired delimiters.

If you want to practice these under real conditions, with a voice-based interviewer that gives rubric feedback on your reasoning alongside your code, SpaceComplexity is built for exactly that.

For the mechanics behind why stacks work, the stack data structure guide covers the array-backed implementation and interview patterns. To recognize which problem calls for a monotonic stack before you start coding, read monotonic stack pattern recognition alongside the monotonic stack deep dive. And if LC 20 felt easier than expected, the Valid Parentheses complexity breakdown explains why the obvious three-line solution gets many candidates rejected.