04 — Stack

Neetcode Week 3. Stacks are LIFO (last-in-first-out). They model recursion, parsing, and the all-important monotonic stack pattern that turns "next greater / smaller" problems from O(n²) into O(n).

Stack basics
Implementation in Python and C++
Pattern: matching / parsing
Pattern: monotonic stack
Pattern: stack of pairs
Walked-through problems
Pitfalls
Practice list

1. Stack basics

A stack supports push, pop, top/peek, and empty. Visualize as a vertical stack of plates.

top → │   ?   │  ← push/pop here
      ├───────┤
      │   3   │
      ├───────┤
      │   1   │
      ├───────┤
      │   7   │  ← bottom (oldest)
      └───────┘

Operation	Cost
`push(x)`	O(1)
`pop()`	O(1)
`top()` / `peek()`	O(1)
`empty()`	O(1)
`size()`	O(1)

Why we need it

Computers use a call stack — every function call pushes a frame, every return pops. Many algorithms that "look recursive" are actually iterative-with-an-explicit-stack:

DFS (depth-first traversal of trees and graphs)
Expression parsing (calculators, compilers)
Bracket matching
Function inlining / tail-call elimination

2. Implementation

Python

Just use a list. Append = push, pop = pop. Don't use pop(0) (that's O(n)).

stack = []
stack.append(1)         # push
stack.append(2)
stack[-1]               # peek (top) → 2
stack.pop()             # pop top → 2
not stack               # is empty? True/False

C++

std::stack is a thin wrapper over deque.

stack<int> st;
st.push(1);
st.top();      // 1
st.pop();      // void in C++ (separates pop and top)
st.empty();
st.size();

⚠️ C++ stack::pop() doesn't return the value. Always do int x = st.top(); st.pop();.

3. Pattern: matching / parsing

Trigger: brackets, opening/closing tags, balanced anything.

Valid Parentheses (Easy)

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
        else:                                # closing
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack                         # all opened must be closed

Trace "({[]})":

( → push: [(]
{ → push: [(, {]
[ → push: [(, {, []
] → pop, expect [ → match: [(, {]
} → pop, expect { → match: [(]
) → pop, expect ( → match: []
return True (empty stack)

Evaluate Reverse Polish Notation (Medium)

"2 1 + 3 *" → push 2, push 1, +(pop pop push 3), push 3, *(pop pop push 9) → 9

def eval_rpn(tokens):
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),    # truncate toward 0 per problem
    }
    for t in tokens:
        if t in ops:
            b = stack.pop()
            a = stack.pop()              # NOTE: a was pushed first, popped second
            stack.append(ops[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

The order a = first popped, b = second popped reverses to "a then b" since stack is LIFO. Bug magnet — write it carefully.

Generate Parentheses (Medium) — see 10-backtracking.md, but uses stack-mental-model.

4. Pattern: monotonic stack

Trigger: "next greater / smaller / span" — for each element, find the next/prev one that's bigger or smaller.

The stack stores indices (or values) in monotonic (always-increasing or always-decreasing) order. As we scan left-to-right, when we see a new element that breaks the monotonicity, we pop until it's restored — and each pop "answers" a query.

Daily Temperatures (Medium)

For each day, how many days until a warmer one? [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]

def daily_temperatures(temps):
    res = [0] * len(temps)
    stack = []                                # indices, temps decreasing top-down
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j                    # we found warmer day for index j
        stack.append(i)
    return res

Trace [73, 74, 75, 71, 69, 72, 76, 73]:

i=0 (73): stack=[0]
i=1 (74): 73<74 → pop 0; res[0]=1. stack=[1]
i=2 (75): 74<75 → pop 1; res[1]=1. stack=[2]
i=3 (71): 75≥71 → push. stack=[2,3]
i=4 (69): 71≥69 → push. stack=[2,3,4]
i=5 (72): 69<72 → pop 4; res[4]=1. 71<72 → pop 3; res[3]=2. 75≥72 → push. stack=[2,5]
i=6 (76): 72<76 → pop 5; res[5]=1. 75<76 → pop 2; res[2]=4. push. stack=[6]
i=7 (73): 76≥73 → push. stack=[6,7]

result = [1, 1, 4, 2, 1, 1, 0, 0]  ✓

Why O(n)? Each index is pushed once and popped at most once. Total stack ops ≤ 2n.

The four flavors

The stack can be increasing or decreasing, and you can scan left-to-right or right-to-left. This determines what query you answer:

Stack (top → bottom)	Scan direction	Pop when...	Each pop yields
Decreasing	left → right	new ≥ top	next greater (to the right)
Increasing	left → right	new ≤ top	next smaller (to the right)
Decreasing	right → left	new ≥ top	next greater (to the left)
Increasing	right → left	new ≤ top	next smaller (to the left)

Memorize one. The others are mirror images.

Largest Rectangle in Histogram (Hard)

Given bar heights [2,1,5,6,2,3], find the largest rectangle area.

6 |       ▓▓
5 |    ▓▓▓▓
4 |    ▓▓▓▓
3 |    ▓▓▓▓    ▓
2 | ▓  ▓▓▓▓ ▓  ▓
1 | ▓▓▓▓▓▓▓ ▓▓▓▓
   ───────────
    2 1 5 6 2 3

Insight: for each bar, we want to find how far left and right it extends as the minimum (i.e., next smaller on each side). Then area = height * (right_smaller - left_smaller - 1).

def largest_rectangle_area(heights):
    stack = []                               # indices, heights increasing
    max_area = 0
    heights.append(0)                        # sentinel forces flush at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            # bar at index `top` extends left to stack[-1]+1 (or 0 if empty)
            # and right to i-1 (because i is the first smaller bar)
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, heights[top] * width)
        stack.append(i)
    heights.pop()                            # restore (optional; pure)
    return max_area

Why this works: when we pop bar top, the bar to its right at index i is strictly smaller (loop condition), and the bar at the new stack top is the nearest smaller-or-equal to its left. So top is the maximum height in the range (stack[-1], i), exclusive on both ends. The rectangle of height heights[top] spans width i - stack[-1] - 1.

Sentinel trick: appending 0 at the end forces every remaining stack element to pop, so we don't need a separate flush loop.

Trapping Rain Water — alternative stack solution (cf. 02)

def trap(heights):
    stack = []                               # indices, heights decreasing
    total = 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] < h:
            mid = stack.pop()
            if not stack: break              # no left wall
            l = stack[-1]
            width = i - l - 1
            bounded_height = min(heights[l], h) - heights[mid]
            total += width * bounded_height
        stack.append(i)
    return total

Less common in interviews than the two-pointer version, but a great example of layered stack-driven thinking.

5. Pattern: stack of pairs

When you need to remember more than just an index/value, push a tuple.

Min Stack (Medium)

Stack with push, pop, top, getMin — all O(1).

class MinStack:
    def __init__(self):
        self.stack = []                      # (value, current_min)
    
    def push(self, x):
        cur_min = x if not self.stack else min(x, self.stack[-1][1])
        self.stack.append((x, cur_min))
    
    def pop(self):
        self.stack.pop()
    
    def top(self):
        return self.stack[-1][0]
    
    def getMin(self):
        return self.stack[-1][1]

Each entry remembers the min of the stack at the time of its insertion. That way, popping never invalidates the min for the new top.

Car Fleet (Medium)

Cars heading to target. Faster cars catch up to slower; they merge into one fleet at the slower car's pace.

def car_fleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)   # nearest target first
    stack = []                                          # arrival times
    for pos, sp in cars:
        time = (target - pos) / sp
        if not stack or time > stack[-1]:
            stack.append(time)                          # forms new (slower) fleet
        # else: catches up to fleet ahead — merges, no push
    return len(stack)

The "stack" here doesn't need to be a stack — it could be a counter — but stack feels natural because you're checking the most recent fleet ahead.

6. Walked-through problems

Generate Parentheses (Medium) — backtracking with stack

n=3 → ["((()))","(()())","(())()","()(())","()()()"]

def generate_parenthesis(n):
    res = []
    stack = []
    
    def backtrack(open_count, close_count):
        if open_count == close_count == n:
            res.append(''.join(stack))
            return
        if open_count < n:
            stack.append('(')
            backtrack(open_count + 1, close_count)
            stack.pop()
        if close_count < open_count:
            stack.append(')')
            backtrack(open_count, close_count + 1)
            stack.pop()
    
    backtrack(0, 0)
    return res

The stack here is conceptual — it tracks the current partial string. Backtracking is "push, recurse, pop." See 10-backtracking.md.

Asteroid Collision (Medium)

Asteroids, positive moves right, negative moves left. Collide when meeting; bigger absolute survives, equal both die.

def asteroid_collision(asteroids):
    stack = []
    for a in asteroids:
        while stack and a < 0 < stack[-1]:           # head-on collision
            if stack[-1] < -a:
                stack.pop()
                continue                              # next stack top might also collide
            elif stack[-1] == -a:
                stack.pop()
            break                                     # current asteroid destroyed (either survived equal or smaller)
        else:
            stack.append(a)
    return stack

The Python while-else is unusual: else runs when the loop didn't break. Here it means: "no collision happened, push the asteroid." Worth knowing this idiom.

7. Pitfalls

Empty-stack peek

stack[-1] raises IndexError if empty. Always guard:

while stack and condition: ...

Forgetting the sentinel

For "Largest Rectangle" and similar, append a 0 (or appropriate boundary) to avoid a separate flush loop. Or initialize stack with -1 for "left boundary."

Pushing wrong type (index vs value)

For most monotonic-stack problems, push indices. You need indices to compute widths/distances and you can always look up arr[idx] when needed.

Off-by-one in width

width = i - stack[-1] - 1 after pop, not i - stack[-1]. Easy to miss.

Recursion-stack vs explicit-stack confusion

Iterative DFS uses an explicit stack but conceptually mimics function-call stack. Don't conflate them.

Mutating list while popping

for x in stack:
    stack.pop()      # iterator confused

Use while stack:.

8. Practice list

#	Problem	Pattern	Difficulty
20	Valid Parentheses	Matching	Easy
155	Min Stack	Stack of pairs	Medium
150	Evaluate Reverse Polish Notation	Calculation	Medium
22	Generate Parentheses	Backtracking	Medium
739	Daily Temperatures	Monotonic stack	Medium
853	Car Fleet	Stack-of-arrival-times	Medium
84	Largest Rectangle in Histogram	Monotonic stack	Hard
735	Asteroid Collision	Simulation with stack	Medium
503	Next Greater Element II	Mono stack on circular	Medium
901	Online Stock Span	Mono stack on stream	Medium

TL;DR ✅

Stack = LIFO, O(1) for push/pop/peek. Python list with append/pop. C++ stack (pop returns void!).
Matching/parsing: brackets, expressions — push openers, match-and-pop on closers.
Monotonic stack turns "next greater/smaller" from O(n²) into O(n). Memorize the four flavors.
Largest Rectangle in Histogram is the gold-standard mono-stack problem; trace it once with a sentinel.
Push indices, not values, to compute widths/distances.
Use sentinels (start with -1, end with 0) to avoid edge-case flush loops.

Next: 05-binary-search.md.

External resources

NeetCode Stack playlist: https://www.youtube.com/playlist?list=PLot-Xpze53lfxD6l5pAGvCD4nPvWKU8Qo
Monotonic stack walkthrough (Errichto): https://www.youtube.com/watch?v=NHoQuvJgQVI
VisuAlgo stack: https://visualgo.net/en/list (Stack section)