Stacks and queues

A stack (last in, first out: a Python list with append and pop) remembers things you must come back to, most recent first. A queue (first in, first out: collections.deque with append and popleft) handles things in arrival order.

Matching brackets

Is a string of brackets ()[]{} balanced?

Push each opening bracket. On a closing bracket, the top of the stack must be its partner. At the end the stack must be empty.

def balanced(s):
    partner = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif not stack or stack.pop() != partner[ch]:
            return False                  # nothing to match, or the wrong partner
    return not stack                      # anything left open is unbalanced

for s in ["([]{})", "([)]", "((", ")("]:
    print(s, balanced(s))

Three ways to fail, all tested: a closing bracket with an empty stack, the wrong partner on top, and opening brackets left at the end. Interviewers love asking which case your code forgot.

The monotonic stack

For each day's temperature, how many days until a warmer one? (Or: the next greater element of each number.)

The brute force looks ahead from every day: O(n²). Instead, keep a stack of the days still waiting for a warmer one. Their temperatures go down from bottom to top: the stack is monotonic. Each new day pops (and answers) every waiting day that is colder, then waits itself.

def days_until_warmer(temps):
    answer = [0] * len(temps)
    waiting = []                          # days still waiting, coldest on top
    for day, t in enumerate(temps):
        while waiting and temps[waiting[-1]] < t:
            cold = waiting.pop()
            answer[cold] = day - cold     # today is that day's first warmer day
        waiting.append(day)
    return answer

print(days_until_warmer([30, 28, 33, 31, 29, 35, 32]))

Each day is pushed once and popped at most once: O(n). Look for this pattern whenever a problem says "the next (or previous) bigger (or smaller) element".

Queues

• Breadth-first search (the graphs lesson) visits nodes in order of distance, with a queue.
• A deque (double-ended queue) adds and removes at both ends in O(1). Keeping a deque of positions in decreasing order of value gives the maximum of every window of size k in O(n): the front is always the current window's maximum.
• Use collections.deque, never list.pop(0), which takes O(n) because it shifts every element.

Mark lesson complete