Interview Prep

Why Interviewers Love Stack Questions

Stack problems are short to state, easy to visualize, and beautiful when you find the trick. They test whether you recognize a last-in, first-out ordering where it is not obvious. A stack encodes the elegant constraint that you can only access the most recently added element.

Because the operations are simple, the hard part is the reasoning: when do you push, when do you pop, and what does the stack actually represent? This reasoning skill transfers across languages and frameworks, which is why interviewers genuinely love them.

Most stack questions reduce to a few recurring patterns: matching, history tracking, monotonic ordering, and expression evaluation. Learn these four patterns and you will recognize the shape of nearly every stack problem. Review the core stack operations

Problem List

Understand why these are usually O(n)

Valid Parentheses

Given a string with the characters (, ), {, }, [, and ], determine if the input string is valid. It is valid if brackets close in the correct order, like ()[]{} and ([{}]), but not (] or ([)].

The stack is the perfect fit. Push each opening bracket. When you see a closing bracket, pop the top opening bracket and verify it matches. If the stack is empty when a closer appears, or if the top does not match, the string is invalid. At the end, the stack must be empty.

def isValid(s):
    stack = []
    mapping = {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in mapping:
            if not stack or stack.pop() != mapping[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

Time: O(n). Space: O(n) for the stack. Why LIFO guarantees correctness

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. The challenge is that popping can remove the current minimum, so you must remember previous minimums.

The standard trick is to maintain two stacks: the data stack and a separate min stack. When pushing a value, also push onto the min stack the smaller of the new value and the current top of the min stack. Popping from the data stack pops from the min stack too, so the min stays consistent.

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):
        if self.stack:
            val = self.stack.pop()
            if val == self.min_stack[-1]:
                self.min_stack.pop()
            return val

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

    def getMin(self):
        return self.min_stack[-1] if self.min_stack else None

All operations run in O(1) time. Space is O(n) for the auxiliary min stack.

Implement Queue Using Stacks

Implement a first-in, first-out queue using only two stacks. A stack is LIFO, so to get FIFO order you must reverse the elements.

Keep one stack for incoming elements and one for outgoing. When you need to pop or peek, if the outgoing stack is empty, transfer all elements from the incoming stack into it, which reverses their order. The top of the outgoing stack is then the front of the queue.

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

    def push(self, x):
        self.input.append(x)

    def pop(self):
        self._move()
        return self.output.pop()

    def peek(self):
        self._move()
        return self.output[-1]

    def empty(self):
        return not self.input and not self.output

    def _move(self):
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

Each element is moved at most once, so the amortized time per operation is O(1).

Evaluate Reverse Polish Notation

Given an array of tokens in Reverse Polish Notation, evaluate it. Operators like +, -, *, and / apply to the two most recent operands.

Scan the tokens. When you see a number, push it onto the stack. When you see an operator, pop the two top numbers, apply the operator, and push the result back. When the scan ends, the stack holds exactly one value, the answer.

def evalRPN(tokens):
    stack = []
    for t in tokens:
        if t in "+-*/":
            b = stack.pop()
            a = stack.pop()
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))
        else:
            stack.append(int(t))
    return stack[0]

Time: O(n). Space: O(n) in the worst case.

Daily Temperatures

Given an array of daily temperatures, return an array where each answer tells how many days you have to wait for a warmer temperature. If none, the answer is 0.

The monotonic stack is the classic solution. The stack holds indices whose temperature is still waiting for a warmer day. As you scan left to right, while the current temperature is warmer than the temperature at the index on top of the stack, pop that index and record the difference.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

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

Largest Rectangle in Histogram

Given an array of bar heights, find the largest rectangle that can fit under the histogram. This is the hardest classic stack problem.

Use a monotonic stack of indices that maintains increasing heights. When a new height is smaller than the height at the top, the bar at the top cannot extend any further to the right, so you pop it and compute the rectangle it forms: its height times the width between the popped index and the new stack top.

def largestRectangleArea(heights):
    stack = []
    heights.append(0)
    max_area = 0
    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

Time: O(n). Space: O(n). Each bar is pushed and popped once.

Trapping Rain Water

Given elevation heights, compute how much water can be trapped between bars after it rains. A bar traps water if taller bars exist on both sides.

The monotonic stack tracks indices of bars in decreasing height order. When the current bar is taller than the top of the stack, a depression exists between two taller bars, so pop and compute the trapped water using the height difference and the horizontal distance.

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            depth = min(height[left], h) - height[bottom]
            water += depth * (i - left - 1)
        stack.append(i)
    return water

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

Next Greater Element

For each element in an array, find the next element to its right that is greater, or -1 if none exists.

Scan the array left to right with a monotonic stack of indices. While the current element is greater than the element at the top of the stack, pop and record the current element as the next greater for the popped index.

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

This version handles circular arrays by scanning twice. Time: O(n). Space: O(n).

Decode String

Given an encoded string like 3[a2[c]], decode it to accaccacc. The rule repeats a substring a given number of times, and the encoding can be nested.

Use two stacks: one for repetition counts and one for the strings built so far. When you see a digit, build the number. When you see [, push the current count and string, then reset. When you see ], pop and append the repeated substring.

def decodeString(s):
    stack = []
    cur_string = ""
    cur_num = 0
    for ch in s:
        if ch.isdigit():
            cur_num = cur_num * 10 + int(ch)
        elif ch == "[":
            stack.append((cur_string, cur_num))
            cur_string = ""
            cur_num = 0
        elif ch == "]":
            prev_string, num = stack.pop()
            cur_string = prev_string + cur_string * num
        else:
            cur_string += ch
    return cur_string

Time: O(n) where n is the length of the decoded output. Space: O(n).

Basic Calculator

Implement a calculator that evaluates a string with +, -, and parentheses, e.g. (1+(4+5+2)-3)+(6+8).

Use a stack to remember the running sign and total when entering parentheses. Push the current result and sign before each (, reset, and restore them when you hit ).

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

Time: O(n). Space: O(n) for the stack of saved parentheses contexts.

Asteroid Collision

Given an array of asteroids, where a positive value moves right and a negative value moves left, determine the state after all collisions. When two asteroids meet, the bigger one survives, and equal sizes destroy both.

Process asteroids with a stack. A collision only happens when the current asteroid moves left and the top of the stack moves right. Resolve each collision by comparing absolute sizes.

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

Time: O(n). Each asteroid is pushed and popped at most once. Space: O(n).

Remove Stars From a String

Given a string where a * removes the nearest character to its left, return the final string.

Push every regular character onto a stack. When you see a *, pop the top character to remove the nearest left neighbor. This is a clean cancellation pattern.

def removeStars(s):
    stack = []
    for ch in s:
        if ch == "*":
            if stack:
                stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

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

Summary of Techniques

Every stack interview problem uses one of a few patterns. Matching problems like valid parentheses resolve on pop. Design problems like Min Stack or Queue Using Stacks use an auxiliary stack. History problems like backspace and undo push and pop as events happen. Expression problems evaluate by pushing operands and popping on operators. And the powerful monotonic stack solves next-greater, daily-temperatures, largest-rectangle, and rain-water problems in linear time.

If you can spot which pattern a problem needs, half the work is done. Master the monotonic stack pattern

Frequently Asked Questions

Why do interviewers love stack questions?

Stacks encode a simple but powerful constraint, LIFO, that solves many real problems elegantly. They test your ability to recognize when a last-in, first-out order is the natural fit for a problem, and they pair well with topics like matching, history, and monotonic ordering. A stack problem is compact, easy to describe, and exposes your reasoning clearly.

When should I use a monotonic stack?

Use a monotonic stack when you need to find the next or previous greater or smaller element for each item in an array. It keeps the stack sorted in a chosen order and processes each element once, giving O(n) time. Classic uses include daily temperatures, next greater element, largest rectangle in a histogram, and trapping rain water.

How do I recognize that a problem needs a stack?

Look for a pattern of cancellation or nesting: matching parentheses, undo history, balanced brackets, or backspaces. Also look for next greater element patterns and expression evaluation with precedence. If the solution requires processing elements in reverse order of arrival, LIFO, a stack is the natural data structure.