Stacks and Search

A program that stores things for later has to decide which one to take back next. Take the newest and you have a stack; take the oldest and you have a queue. That one choice decides what a program can answer: whether brackets match, which earlier value is the nearest smaller one, and whether a search finds the shortest route or merely a route.

The worked examples here are an expression evaluator, a "previous smaller price" scan, and a knight's shortest path. The lab uses the same structures on brackets, temperatures, a maze and a cache.

Stacks: the newest thing first

A Python list is a good stack: append pushes onto the top and pop() takes from the top, both O(1). A stack is the right tool whenever the most recent unfinished thing must be finished first. Reverse Polish notation is a clean example: 3 4 + 2 * means (3 + 4) × 2.

def evaluate(tokens):
    stack = []
    for token in tokens.split():
        if token in "+-*":
            right = stack.pop()
            left = stack.pop()
            stack.append(left + right if token == "+" else left - right if token == "-" else left * right)
        else:
            stack.append(int(token))
    return stack.pop()

assert evaluate("3 4 + 2 *") == 14
assert evaluate("5 1 2 + 4 * + 3 -") == 14

Each operator takes the two most recent results — exactly what a stack hands back. Matching brackets works the same way: an opener waits on the stack until the closer that belongs to it arrives, and a counter alone cannot do it, because ([)] has the right number of each bracket in the wrong order.

Monotonic stacks: answering many questions at once

For each day's price, what is the nearest earlier price that was lower? Scanning back from every day is O(n²). A stack can answer every day in one pass if it keeps only the prices that could still be someone's answer:

def previous_lower(prices):
    answer = []
    stack = []                         # indexes; their prices rise from bottom to top
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] >= price:
            stack.pop()                # can never be a later day's answer: price is lower and nearer
        answer.append(prices[stack[-1]] if stack else None)
        stack.append(i)
    return answer

assert previous_lower([5, 3, 4, 6, 2, 7]) == [None, None, 3, 4, None, 2]

Why may a price be thrown away? If today's price is lower than or equal to an earlier one, every later day will reach today first, and today is at least as low. The earlier price can never be anyone's answer again. That gives the invariant:

The prices on the stack strictly increase from bottom to top, and each one is still a possible answer for some later day.

Each index is pushed once and popped at most once, so the whole scan is O(n) even with a while inside the for. The lab's "warmer day" exercise turns this around — it keeps days that are still waiting for an answer — but the argument about pushes and pops is the same.

Queues and breadth-first search

A queue takes the oldest item first. In Python use collections.deque: append adds at the back and popleft takes from the front, both O(1). A list's pop(0) also takes from the front but shifts every remaining item, O(n) each time.

A queue is what makes breadth-first search (BFS) find shortest paths. Here a knight on an 8 × 8 board finds the fewest moves between two squares:

from collections import deque

JUMPS = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]

def knight_moves(start, goal, size=8):
    distance = {start: 0}              # also the set of squares already reached
    queue = deque([start])
    while queue:
        square = queue.popleft()
        if square == goal:
            return distance[square]
        for dr, dc in JUMPS:
            r, c = square[0] + dr, square[1] + dc
            if 0 <= r < size and 0 <= c < size and (r, c) not in distance:
                distance[(r, c)] = distance[square] + 1   # recorded when it joins
                queue.append((r, c))
    return -1

assert knight_moves((0, 0), (0, 0)) == 0
assert knight_moves((0, 0), (1, 2)) == 1
assert knight_moves((0, 0), (7, 7)) == 6

BFS explores in rings: every square one move away, then every square two moves away, and so on. The queue keeps that order:

Squares leave the queue in order of their distance from the start, and the distances in the queue differ by at most one.

So the first time the search reaches a square is along a shortest route, and that is when its distance is recorded — when it joins the queue. Recording it only when it leaves would let the same square join several times.

Swap popleft() for pop() and the queue becomes a stack. The search then runs deep before wide (depth-first search): it still visits every reachable square, but the first route it finds to a square is often a long way round, so the distances are wrong. Depth-first search is the right tool for "is there any route?", "visit everything" and exploring puzzles; breadth-first search is the tool for "what is the fewest steps?".

To rebuild the route itself, store came_from[square] instead of (or beside) the distance, then walk back from the goal and reverse. The lab's maze does exactly that.

Caches: forgetting the right thing

A cache keeps a few recent answers so a program need not recompute them, and when it is full it must forget one. A least-recently-used (LRU) cache forgets the key that has gone longest without being used. Both reading and writing count as using a key.

Doing that in O(1) needs two structures working together: a dictionary finds a key's entry at once, and a doubly linked list keeps entries in order of use, so the least recent one is always at the front and any entry can be unlinked and moved to the back in constant time. Python's OrderedDict packages exactly that design — a dictionary that remembers order, with move_to_end(key) and popitem(last=False) — which is why the lab builds the cache on it. In an interview, be ready to explain the hash-map-plus-linked-list idea underneath.

What it costs

Where it goes wrong

• list.pop(0) as a queue. It works and quietly makes BFS O(n²).
• Marking a square visited when it leaves the queue. It can join several times first.
• A stack where a queue was needed. The search finds a route, not the shortest.
• Forgetting leftovers. A bracket checker must also reject openers still on the stack at the end.

In the lab

The lab matches brackets with a stack and replays your function bracket by bracket, answers "how many days until a warmer day?" with a monotonic stack whose checks count how often each day is read, searches a maze breadth-first and rebuilds the shortest path from came_from, and builds an LRU cache on OrderedDict. The mastery challenge is a search from several starting points at once that names no technique; one of its questions asks when a cell should be given its distance, and why.