Learn interview-prep-45

Stacks

Browsing without an account — progress is saved in this browser only.Sign in to save it

Stacks

Reading120 min

Picture a stack of plates on a kitchen counter, 20 plates high. You add a new plate on top, and you take one off the top too. You never grab a plate from the middle without knocking the rest over. That is a stack, one of the simplest data structures there is, and the monotonic stack pattern built on top of it solves a whole family of "next greater or smaller element" problems in O(n), about 20 steps for 20 elements, that look like they need O(n²), about 400 comparisons, at first glance.

LIFO principle

Like the plate stack, a data-structure stack supports two core operations, both O(1) (one step, regardless of how many plates are underneath): push (add to the top) and pop (remove from the top). Last-In-First-Out (LIFO) means the most recently added element leaves first, the same way the plate you set down last is the one you pick back up first. A queue (FIFO, First-In-First-Out) is the opposite: like a line at a coffee shop, the oldest person waiting is served first.

stack = []
stack.append(1)   # push
stack.append(2)
stack.append(3)
stack.pop()        # removes 3
stack[-1]          # peek: 2, without removing

Python's list is a perfectly good stack (append/pop from the end are both O(1) amortized). Do not use list.insert(0, x) or list.pop(0) as a stack; those are O(n) because they shift every element.

Remember: a stack is last-in-first-out. In Python, append/pop from the end. Never insert or pop from the front of a list-backed stack.

Stack vs recursion

Picture a stack of sticky notes, one added every time you pause a task to start a smaller sub-task, and removed the moment that sub-task finishes and you go back to the one below it. That is exactly what a computer does on every recursive function call: it is an implicit stack. Each call pushes a new frame, its local variables and where to return to, onto the call stack, and returning pops it off. Any recursive algorithm can be rewritten iteratively with an explicit stack you manage yourself. That matters for two reasons.

Deep recursion can hit Python's recursion limit (1,000 calls deep by default) or overflow the real call stack, the same way a pile of 1,000 sticky notes eventually topples. An explicit stack has no such limit, bounded only by however much heap memory is free.
Interviewers sometimes ask directly for the iterative version, to check that you understand what recursion is doing underneath.

The mechanical translation: whatever you would pass as arguments to the recursive call, push as a tuple onto an explicit stack instead. A while stack: loop replaces the call.

# Recursive DFS
def dfs_recursive(node, visited):
    if node in visited:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs_recursive(neighbor, visited)

# Iterative DFS using an explicit stack
def dfs_iterative(start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in node.neighbors:
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

Remember: every recursive call is a push; every return is a pop. An explicit stack turns recursion into a loop with no depth limit.

Monotonic stack pattern

Picture 100 people lined up by height, and every time a taller person walks up to join the back of the line, everyone shorter than them steps out, because they just found the next taller person behind them. Whoever is left in line is always ordered shortest to tallest. A monotonic stack works the same way: it keeps its elements in strictly increasing or strictly decreasing order at all times. When a new element would break that order, you pop elements off the top until the order holds again, and each pop is a signal: the element just popped just found its next greater (or smaller) element.

This is the trick behind "next greater element" style problems. Instead of scanning forward from each element to find the next bigger one, which for 100 elements can mean close to 10,000 comparisons (O(n²)), you keep a stack of indices whose answer is not known yet, and resolve them as you scan once, left to right, about 100 steps total (O(n), since each index is pushed once and popped at most once).

def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []  # indices, values decreasing bottom to top
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

Stack using a linked list

Arrays make a fine stack, but interviewers sometimes ask for one implemented over a singly linked list, where push and pop happen at the head so both stay O(1) with no resizing:

class StackNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

class LinkedListStack:
    def __init__(self):
        self.head = None
        self.size = 0

    def push(self, val) -> None:
        self.head = StackNode(val, self.head)
        self.size += 1

    def pop(self):
        if not self.head:
            raise IndexError("pop from empty stack")
        val = self.head.val
        self.head = self.head.next
        self.size -= 1
        return val

    def peek(self):
        if not self.head:
            raise IndexError("peek from empty stack")
        return self.head.val

    def is_empty(self) -> bool:
        return self.head is None

No amortized cost here. Every operation is worst-case O(1) since there is never a resize, at the cost of the per-node pointer overhead an array-backed stack does not pay.

Remember: a monotonic stack turns "find the next greater element for everyone" into one O(n) pass. Each index is pushed once, popped at most once.

Valid Parentheses

Valid Parentheses (LeetCode 20)

Intuition: Every closing bracket must match the most recently opened, unclosed bracket. "Most recent unmatched" is exactly what a stack tracks.

Approach: Push opening brackets. On a closing bracket, pop and check it matches the expected opener; a mismatch or an empty stack means invalid. The string is valid only if the stack is empty at the end.

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

Complexity: Time O(n), space O(n) worst case (all openers).

Common mistakes:

Forgetting to check not stack before popping on a closing bracket. A lone ")" would crash or misbehave without that guard.
Forgetting the final not stack check. A string like "(((" never triggers a mismatch mid-scan, but is still invalid.

Remember: push openers, pop and match on closers, and the stack must end empty.

Daily Temperatures

Daily Temperatures (LeetCode 739)

Intuition: For each day, find how many days until a warmer temperature. This is "next greater element," but returning the distance instead of the value.

Approach: A monotonic decreasing stack of indices. When the current temperature beats the temperature at the stack's top index, pop and record current_index - popped_index as the wait.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices with temps not yet resolved, decreasing order
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)
    return result

Complexity: Time O(n): each index pushed once, popped at most once. Space O(n) worst case (strictly decreasing input).

Common mistakes:

Brute-forcing with a nested loop (O(n²)). Works, but it is the naive baseline interviewers expect you to improve on.
Storing values instead of indices on the stack. You need the index to compute the distance, not the temperature.

Remember: store indices, not values, so you can compute the distance once you find the warmer day.

Largest Rectangle in Histogram

Largest Rectangle in Histogram (LeetCode 84)

Intuition: For each bar, the largest rectangle using that bar as its shortest (limiting) height extends as far left and right as neighboring bars stay at least as tall. A monotonic increasing stack finds, for each bar, the nearest shorter bar on both sides in a single O(n) pass; those boundaries set the max width for that bar's height.

Approach: Keep a stack of indices with increasing heights. When the current bar is shorter than the stack's top, pop and compute the area using the popped bar's height, with width equal to the current index minus the new stack top's index minus 1 (or just the current index if the stack is empty). Append a sentinel height of 0 at the end to flush the remaining bars.

def largest_rectangle_area(heights: list[int]) -> int:
    stack = []  # indices, increasing height
    max_area = 0
    heights = heights + [0]  # sentinel to flush the stack

    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

Complexity: Time O(n): each index pushed and popped once. Space O(n).

Common mistakes:

Forgetting the sentinel 0 at the end, which leaves bars still on the stack unresolved.
Getting the width formula wrong. It is i - stack[-1] - 1 (excluding both boundary indices), not i - stack[-1].
Trying brute force (checking every pair of left/right boundaries, O(n²) or O(n³)) as the final answer instead of a starting point.

Remember: a monotonic increasing stack finds each bar's nearest shorter neighbor on both sides in one pass. Add a sentinel zero to flush the stack at the end.

Min Stack

Min Stack (LeetCode 155)

Intuition: A normal stack gives O(1) push, pop, and top, but O(n) minimum, since you would have to scan. Track the running minimum alongside each element, so every push carries "the minimum including me," giving O(1) minimum retrieval too.

Approach: Store (value, current_min) pairs in a single stack, where current_min is the smaller of the new value and the previous entry's minimum.

class MinStack:
    def __init__(self):
        self.stack = []  # each entry: (value, min_so_far)

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

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

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

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

Complexity: Time O(1) for every operation. Space O(n): double the per-element storage, for the min tracking.

Common mistakes:

Recomputing min(self.stack) inside getMin(). Correct, but O(n), defeating the purpose.
Using one global min variable with no way to restore the previous minimum on pop(). That only works if you never pop the current minimum, which is not guaranteed.

Remember: store the running minimum alongside every value, so popping an old minimum automatically reveals the one before it.