4. Stacks & Queues

What Interviewers Test Here

• Stack for "most recent unsettled" problems (brackets, temperatures, histogram)
• Monotonic stack to find next greater/smaller element in $O(n)$
• Queue / BFS for shortest path, level-order traversal

from collections import deque

# --- Valid Parentheses ---
def is_valid(s: str) -> bool:
    stack = []
    close = {')': '(', '}': '{', ']': '['}
    for c in s:
        if c in '({[':
            stack.append(c)
        elif not stack or stack[-1] != close[c]:
            return False
        else:
            stack.pop()
    return not stack

# --- Monotonic stack: next greater element ---
def next_greater(arr: list[int]) -> list[int]:
    result = [-1] * len(arr)
    stack  = []   # holds indices waiting for their "next greater"
    for i, x in enumerate(arr):
        while stack and arr[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

# --- Sliding window maximum (deque) ---
def sliding_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()   # indices, decreasing by value
    result = []
    for i, x in enumerate(nums):
        while dq and dq[0] < i - k + 1: dq.popleft()
        while dq and nums[dq[-1]] < x:  dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

---

Conceptual Q&A

Q1: "Given an array of daily temperatures, find how many days until a warmer day for each day."

Walkthrough:

"For each day, I'm looking for the next day with a higher temperature — a 'next greater element' problem.

Brute force: for each day, scan forward until a warmer day. $O(n^2)$.

Optimised: I'll use a monotonic stack. I maintain a stack of days that are 'waiting' for a warmer day. I push each day's index onto the stack. When I encounter a day warmer than the top of the stack, that top has found its answer. The stack stays in decreasing temperature order.

Why does this work? Any day still on the stack when I process a warmer day must be colder — otherwise it would have been popped already. $O(n)$ time, $O(n)$ space."

def daily_temperatures(temps: list[int]) -> list[int]:
    result = [0] * len(temps)
    stack  = []   # indices of days waiting for a warmer day

    for today in range(len(temps)):
        # Today is warmer than all days on the stack — answer them
        while stack and temps[stack[-1]] < temps[today]:
            cold_day = stack.pop()
            result[cold_day] = today - cold_day
        stack.append(today)
    # Days remaining in stack never found a warmer day → result stays 0
    return result

# Trace: temps = [73, 74, 75, 71, 69, 72, 76, 73]
# Day 0 (73): push 0.  stack=[0]
# Day 1 (74): 74>73 → pop 0, result[0]=1. push 1.  stack=[1]
# Day 2 (75): 75>74 → pop 1, result[1]=1. push 2.  stack=[2]
# Day 3 (71): push 3.  stack=[2,3]
# Day 4 (69): push 4.  stack=[2,3,4]
# Day 5 (72): 72>69 → pop 4, result[4]=1. 72>71 → pop 3, result[3]=2. push 5. stack=[2,5]
# Day 6 (76): 76>72 → pop 5, result[5]=1. 76>75 → pop 2, result[2]=4. push 6. stack=[6]
# Day 7 (73): push 7.  stack=[6,7]
# Result: [1, 1, 4, 2, 1, 1, 0, 0]

---

Q2: "Design a stack that supports push, pop, and getMin in O(1)."

Walkthrough:

"Normal stack doesn't track minimum — to find it I'd need $O(n)$. I need to store extra information.

Key insight: the minimum can only change when I push or pop. I'll use a second stack that tracks the minimum at each level. When I push a value, I also push min(value, current_min) onto the min stack. When I pop, I pop both stacks in sync. getMin just peeks at the min stack top — $O(1)$."

class MinStack:
    def __init__(self):
        self._stack:     list[int] = []
        self._min_stack: list[int] = []

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

    def pop(self) -> None:
        self._stack.pop()
        self._min_stack.pop()

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

    def get_min(self) -> int:
        return self._min_stack[-1]   # O(1) always

---