Stacks & Queues Master Recap — All Patterns & Templates

Stacks & Queues — Master Recap

Problems 251–300 | 45+ posts | Easy × 10, Medium × 25, Hard × 10

The 7 Core Patterns

Pattern Templates

Monotonic Decreasing Stack (Next Greater)

stack = []  # stores indices
res = [-1] * n
for i in range(n):
    while stack and nums[stack[-1]] < nums[i]:
        res[stack.pop()] = nums[i]
    stack.append(i)

Monotonic Increasing Stack (Largest Rectangle)

heights = [0] + heights + [0]
stack = [0]; ans = 0
for i in range(1, len(heights)):
    while heights[stack[-1]] > heights[i]:
        h = heights[stack.pop()]
        w = i - stack[-1] - 1
        ans = max(ans, h * w)
    stack.append(i)

Multi-Source BFS

queue = deque(all_source_nodes)
visited = set(all_source_nodes)
while queue:
    r, c = queue.popleft()
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        nr, nc = r+dr, c+dc
        if valid and not visited:
            visited.add((nr,nc)); queue.append((nr,nc))

Min Stack

class MinStack:
    def push(self, val):
        self.stack.append(val)
        self.min_stack.append(min(val, self.min_stack[-1] if self.min_stack else val))

Sliding Window Maximum (Deque)

dq = deque()  # indices, monotone decreasing values
for i in range(n):
    while dq and dq[0] <= i-k: dq.popleft()      # expire
    while dq and nums[dq[-1]] < nums[i]: dq.pop() # maintain
    dq.append(i)
    if i >= k-1: res.append(nums[dq[0]])

Topological Sort BFS (Kahn's)

queue = deque(nodes with in_degree 0)
while queue:
    node = queue.popleft(); order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0: queue.append(neighbor)

Big O Reference

Problem Index by Pattern

Monotonic Stack

10 Daily Temperatures · 11 NGE I · 12 NGE II · 13 Stock Span · 14 Remove K Digits · 19 Sum Subarray Mins · 28 132 Pattern · 29 Visible People · 38 Largest Rectangle · 39 Maximal Rectangle · 44 Trap Rain Water

BFS / Graph

22 Rotting Oranges · 23 Number of Islands · 24-25 Course Schedule · 26 Word Ladder · 31 Pacific Atlantic · 34 Walls & Gates · 43 Serialize Tree

Design

02 Stack via Queue · 03 Queue via Stacks · 04 Min Stack · 08 Recent Calls · 30 Circular Queue · 35 Nested Iterator · 37 Hit Counter · 41 Freq Stack · 42 Median Stream

Deque

17 Sliding Window Max · 32 Jump Game VI · 33 Shortest Subarray K

Expression Evaluation

15 Decode String · 16 Evaluate RPN · 27 Basic Calculator II · 40 Basic Calculator I

MAANG Interview Priority

Must-Know:

• Valid Parentheses (bracket matching)
• Daily Temperatures (mono stack)
• Sliding Window Maximum (deque)
• Largest Rectangle in Histogram (mono stack)
• Max Frequency Stack (design)
• Median from Data Stream (two heaps)
• Course Schedule (topo sort)

High Value:

• Basic Calculator I & II (expression parsing)
• Word Ladder (BFS shortest path)
• Serialize/Deserialize Binary Tree (BFS design)

Common Mistakes

1. Mono stack direction: Decreasing for "next greater", increasing for "area" problems
2. Stack stores indices (not values) so you can compute width/position
3. Multi-source BFS: Add ALL sources to queue BEFORE starting BFS
4. Kahn's topo sort: Only enqueue when in-degree reaches EXACTLY 0
5. Min Stack: Both stacks must stay in sync — always push/pop both together
6. Deque window: Check dq[0] <= i-k (expired), then nums[dq[-1]] < nums[i] (smaller)

Next Section → Binary Search (problems 301–345)