Stack & Queue Patterns — Comprehensive Guide

Stacks and queues are deceptively powerful. Beyond basic LIFO/FIFO operations, they unlock efficient solutions to problems involving nearest elements, sliding windows, expression parsing, and histogram areas -- problems that would otherwise require O(N^2) brute force.

Quick Navigation: “I need to…”

From-Scratch Idea: What Makes a Problem Stack or Queue

Before memorizing eleven sections, internalize the one question that routes every problem here:

“When I process element i, do I need to react to earlier elements that are still ‘waiting for an answer’ — and does the most recent unanswered one matter first (stack), or the oldest (queue)?”

That single ordering choice — LIFO vs FIFO — is the whole pattern. Everything else is what you do at the moment of popping.

The Two-Question Identify Test

1. Is there a “pending until resolved” relationship? Each element sits around unanswered until some later element resolves it. “Next greater”, “matching close-bracket”, “bar’s right wall”, “warmer day” — all are “this waits for its trigger”.
2. Which pending element resolves first — newest or oldest?
   • Newest first → Stack. The bracket you opened last must close first. The bar just to your left is the first wall you hit. Nesting, nearest-neighbor, innermost-first ⇒ LIFO.
   • Oldest first → Queue. The request that arrived first expires first. Level d must finish before level d+1. Time-order, level-order, arrival-order ⇒ FIFO.

If neither holds — no pending relationship, no LIFO/FIFO ordering — it is not a stack/queue problem (reach for a heap, hash map, or sort instead).

The Mental Shift

The One Template Behind Almost All of It

for each element x (index i):
    # (stack) pop everyone whose wait x just ended:
    while stack not empty AND x violates the monotonic invariant:
        popped = stack.pop()
        COMPUTE popped's answer   # x is popped's next-greater / right-wall / ...
    stack.append(i)              # x now waits for ITS trigger

Swap the invariant (< vs >, strict vs non-strict) and swap what COMPUTE does — that’s the difference between “next greater”, “largest rectangle”, and “trapping rain water”. They are one algorithm wearing three costumes.

★ Insight ─────────────────────────────────────

• Store indices, not values. arr[idx] recovers the value any time, but a bare value can’t recover where it was — and widths, distances, and window-eviction all need the position. Every monotonic-stack solution below pushes i, never arr[i].
• The pop is where the answer is born. You never learn an element’s answer while pushing it; you learn it the moment a later element forces it off the stack. That “resolved-on-eviction” event is the single unifying idea across §2, §6, §7, and §10.
• Amortized O(N), not O(N²), because each index is pushed once and popped once. The inner while looks nested, but its total work across the whole outer loop is bounded by 2N — the reason this pattern exists. ─────────────────────────────────────────────────

LeetCode ↔ Classic (CSES/CP) Translation

Master LeetCode Comparison Table

Each row below gets a full walkthrough — statement, the exact template it plugs into, an executed trace, and an ★ Insight.

Table of Contents

1. Stack & Queue Fundamentals
2. Monotonic Stack
3. Parentheses and Bracket Matching
4. Expression Evaluation
5. Monotonic Deque (Sliding Window Min/Max)
6. Histogram Problems
7. Stock Span and Daily Temperatures
8. Queue Patterns
9. Augmented Stacks and Queues
10. Trapping Rain Water
11. Pattern Recognition Cheat Sheet

1. Stack & Queue Fundamentals

Stack (LIFO -- Last In, First Out)

Push 1, Push 2, Push 3:

  |  3  |  <-- top
  |  2  |
  |  1  |
  +-----+

Pop -> 3, Pop -> 2, Pop -> 1

# Python: use a list
stack = []
stack.append(1)    # push
stack.append(2)
top = stack[-1]    # peek: 2
stack.pop()        # pop: 2

Queue (FIFO -- First In, First Out)

Enqueue 1, 2, 3:

  Front -> [1, 2, 3] <- Back

Dequeue -> 1, Dequeue -> 2, Dequeue -> 3

from collections import deque
queue = deque()
queue.append(1)     # enqueue (right)
queue.append(2)
front = queue[0]    # peek: 1
queue.popleft()     # dequeue: 1

Deque (Double-Ended Queue)

Can push/pop from BOTH ends in O(1):

  Front <-> [1, 2, 3] <-> Back

appendleft / popleft  |  append / pop

from collections import deque
dq = deque()
dq.append(3)        # add right
dq.appendleft(1)    # add left
dq.pop()            # remove right: 3
dq.popleft()        # remove left: 1

Why Not Just Use Arrays?

Use deque whenever you need O(1) operations at both ends.

2. Monotonic Stack

The single most important stack pattern. Solves a family of “nearest” problems in O(N).

The Core Idea

Concrete motivation: for each day’s temperature, find how many days until a warmer day (LC 739). The naive approach scans right from every day → O(N^2). A monotonic stack lets each element be pushed and popped at most once, so the whole thing runs in O(N).

A monotonic stack maintains elements in sorted order (either increasing or decreasing). When a new element violates the order, pop elements until the invariant is restored. The popped elements have found their “answer.”

Monotonic DECREASING stack (for next greater element):

Array: [2, 1, 5, 6, 2, 3]

Process each element:
  2: stack empty, push             stack: [2]
  1: 1 < 2 (ok, maintain order)   stack: [2, 1]
  5: 5 > 1, pop 1 (next greater of 1 is 5)
     5 > 2, pop 2 (next greater of 2 is 5)
     push 5                        stack: [5]
  6: 6 > 5, pop 5 (next greater of 5 is 6)
     push 6                        stack: [6]
  2: 2 < 6, push                   stack: [6, 2]
  3: 3 > 2, pop 2 (next greater of 2 is 3)
     push 3                        stack: [6, 3]
  End: remaining in stack have no next greater -> -1

Result: [5, 5, 6, -1, 3, -1]

2.1 Next Greater Element

Problem: For each element, find the first element to its right that is larger.

def next_greater(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices, elements in decreasing order

    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

arr:    [2, 1, 5, 6, 2, 3]
result: [5, 5, 6,-1, 3,-1]

2.2 Next Smaller Element

Flip the comparison. Use a monotonic increasing stack.

def next_smaller(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices, elements in increasing order

    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

arr:    [4, 8, 5, 2, 25]
result: [2, 5, 2,-1, -1]

2.3 Previous Greater Element

Iterate forward (same direction), but the answer is what’s already on the stack when you push.

def previous_greater(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # decreasing stack

    for i in range(n):
        while stack and arr[stack[-1]] <= arr[i]:
            stack.pop()
        result[i] = arr[stack[-1]] if stack else -1
        stack.append(i)

    return result

arr:    [10, 4, 2, 20, 40, 12, 30]
result: [-1,10,4, -1, -1, 40, 40]

2.4 Previous Smaller Element

def previous_smaller(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # increasing stack

    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        result[i] = arr[stack[-1]] if stack else -1
        stack.append(i)

    return result

Strict vs Non-Strict (< vs <=)

The comparison operator in the while condition decides how ties (equal values) are handled — and getting it wrong is the #1 beginner monotonic-stack bug.

Look at next_greater: it pops while arr[stack[-1]] < arr[i] (strict <). Because the comparison is strict, an equal element does not trigger a pop, so equal elements never resolve each other.

arr = [2, 2, 3]   (next greater, strict '<')

i=0: push 0                          stack: [0]
i=1: arr[0]=2 < arr[1]=2 ? No        push 1, stack: [0, 1]
i=2: arr[1]=2 < 3 ? Yes -> result[1]=3
     arr[0]=2 < 3 ? Yes -> result[0]=3
     push 2                          stack: [2]

Result: [3, 3, -1]   (each 2's "next greater" is the 3, not the other 2)

Now change the operator to <= (non-strict):

arr = [2, 2, 3]   (with '<=')

i=1: arr[0]=2 <= arr[1]=2 ? Yes -> pop 0, result[0]=2   (the second 2 answers the first)
...

Result: [2, 3, -1]

The strict version answers “next strictly greater”; the non-strict version answers “next greater-or-equal”. Same code, one operator, two different problems. Pick the operator that matches the tie semantics you actually want (and mirror the choice for the smaller-element and previous-element variants).

The Complete Monotonic Stack Family

The Key Insight

When you pop element X because of element Y:
  - Y is the NEXT greater/smaller of X (depending on stack type)
  - The new stack top is the PREVIOUS greater/smaller of X

One pass gives you TWO pieces of information per element!

Circular Array Variant

For circular arrays, iterate the array twice (indices 0 to 2N-1):

def next_greater_circular(arr):
    n = len(arr)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        while stack and arr[stack[-1]] < arr[i % n]:
            idx = stack.pop()
            result[idx] = arr[i % n]
        if i < n:
            stack.append(i)

    return result

arr:    [1, 2, 1]
result: [2,-1, 2]  (circular: after arr[2]=1, next is arr[0]=1, then arr[1]=2)

Walkthrough — LC 496: Next Greater Element I

This template solves: LC 496, 503 (circular), 739, 1019.

Full statement. You are given two arrays nums1 and nums2 where nums1 is a subset of nums2 (all values distinct). For each x in nums1, find the first element to the right of x in nums2 that is greater than x. If none exists, answer -1. Return the answers in nums1’s order.

Example: nums1 = [4,1,2], nums2 = [1,3,4,2] → [-1, 3, -1]. (In nums2: right of 4 nothing bigger; right of 1 is 3; right of 2 nothing bigger.)

Pattern-focused solution. Ignore the nums1-is-a-subset dressing — that is just a lookup at the end. The engine is next-greater over nums2, the exact next_greater from §2.1. Precompute every element’s next-greater into a hash map in one monotonic-stack pass, then answer each nums1 query in O(1).

def nextGreaterElement(nums1, nums2):
    nge = {}            # value -> its next greater
    stack = []          # decreasing stack of VALUES (safe here: distinct)
    for x in nums2:
        while stack and stack[-1] < x:
            nge[stack.pop()] = x     # x is the answer for everyone it evicts
        stack.append(x)
    # leftovers in stack never found a greater -> default -1
    return [nge.get(x, -1) for x in nums1]

Trace over nums2 = [1, 3, 4, 2]:

x=1: stack empty            push 1        stack: [1]
x=3: 1<3  pop 1, nge[1]=3   push 3        stack: [3]
x=4: 3<4  pop 3, nge[3]=4   push 4        stack: [4]
x=2: 4<2? no                push 2        stack: [4, 2]
end: 4 and 2 unresolved -> nge.get = -1

nge = {1:3, 3:4}
nums1=[4,1,2] -> [nge.get(4,-1), nge.get(1,-1), nge.get(2,-1)] = [-1, 3, -1]  ✓

★ Insight ─────────────────────────────────────

• This is the only place values-on-the-stack is safe — the problem guarantees distinct elements, so a value uniquely identifies its slot. The instant duplicates are possible (LC 503) revert to storing indices; two equal values would otherwise overwrite each other in nge.
• The “subset” wrapper is a decoy. Newcomers try to walk nums1 and search nums2 per query → O(n·m). Recognizing that the real work is one next-greater sweep over nums2 collapses it to O(n+m). Identify the engine, discard the framing.
• LC 503 (circular) is the same loop run over 2n indices with i % n — the only structural change in the whole family. Master this one and the circular variant is a one-line diff. ─────────────────────────────────────────────────

3. Parentheses and Bracket Matching

Valid Parentheses

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return len(stack) == 0

Minimum Removals to Make Valid

def min_removals(s):
    stack = []  # indices of unmatched parentheses

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack and s[stack[-1]] == '(':
                stack.pop()
            else:
                stack.append(i)

    return len(stack)  # all unmatched

Longest Valid Parentheses

def longest_valid_parentheses(s):
    stack = [-1]  # sentinel: index before the start of current valid sequence
    max_len = 0

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # new sentinel
            else:
                max_len = max(max_len, i - stack[-1])

    return max_len

s = ")()())"

i=0 ')': pop -1, stack empty -> push 0 as sentinel  stack: [0]
i=1 '(': push 1                                      stack: [0, 1]
i=2 ')': pop 1, length = 2-0 = 2                     stack: [0]
i=3 '(': push 3                                      stack: [0, 3]
i=4 ')': pop 3, length = 4-0 = 4                     stack: [0]
i=5 ')': pop 0, stack empty -> push 5                 stack: [5]

Answer: 4

Score of Parentheses

() = 1
(()) = 2 * 1 = 2
()() = 1 + 1 = 2
(()(()))  = 2 * (1 + 2*1) = 6

def score_of_parentheses(s):
    stack = [0]  # current depth's score

    for ch in s:
        if ch == '(':
            stack.append(0)  # start new depth
        else:
            inner = stack.pop()
            stack[-1] += max(1, 2 * inner)

    return stack[0]

Walkthrough — LC 20: Valid Parentheses

This template solves: LC 20, 921 (min add to make valid), 1249 (min removals), 32 (longest valid).

Full statement. Given a string s of only ()[]{}, decide if it is valid: every open bracket is closed by the same type, and brackets close in the correct order (innermost first). "()[]{}" → true; "(]" → false; "([)]" → false (wrong order); "{[]}" → true.

Pattern-focused solution. This is the purest LIFO problem in the guide — no monotonic invariant, just matching. An open bracket is a promise you must later fulfil; the most recent promise must be fulfilled first (nesting = LIFO). Push opens; on a close, the top must be its partner or the string is invalid.

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}   # close -> required open
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False            # nothing to match, or wrong type/order
            stack.pop()
    return not stack                     # leftover opens = unbalanced

Trace over "([)]" (the tricky wrong-order case):

'(' : push               stack: ['(']
'[' : push               stack: ['(', '[']
')' : top is '[', but ')' needs '('  ->  MISMATCH, return False   ✓

versus "{[]}" (valid nesting):

'{' : push               stack: ['{']
'[' : push               stack: ['{', '[']
']' : top '[' matches    pop     stack: ['{']
'}' : top '{' matches    pop     stack: []
end: stack empty -> True   ✓

★ Insight ─────────────────────────────────────

• Order-correctness is free from the stack. "([)]" has balanced counts of every bracket yet is invalid — a counter can’t catch it. The LIFO discipline enforces “innermost closes first” automatically: that is exactly why a stack, not a frequency map, is the right tool.
• Two ways to fail, one to succeed. Reject on a close with an empty stack () with nothing open) or a type mismatch; accept only if the stack ends empty (no dangling opens). Beginners forget the final not stack check and wrongly pass "(((".
• The whole family is this skeleton with a richer payload. LC 1249 pushes indices of unmatched brackets to know what to delete; LC 32 pushes a sentinel index to measure valid-run length. Same push-open / pop-on-match spine (see the two variants above this walkthrough). ─────────────────────────────────────────────────

4. Expression Evaluation

Infix Evaluation (with precedence)

Input: "3 + 2 * 4 - 1"
       = 3 + 8 - 1
       = 10

Use two stacks: one for numbers, one for operators.

def evaluate(expression):
    def precedence(op):
        if op in ('+', '-'):
            return 1
        if op in ('*', '/'):
            return 2
        return 0

    def apply_op(ops, vals):
        op = ops.pop()
        b = vals.pop()
        a = vals.pop()
        if op == '+': vals.append(a + b)
        elif op == '-': vals.append(a - b)
        elif op == '*': vals.append(a * b)
        elif op == '/': vals.append(int(a / b))

    vals = []
    ops = []
    i = 0
    tokens = expression.replace(' ', '')

    while i < len(tokens):
        if tokens[i].isdigit():
            num = 0
            while i < len(tokens) and tokens[i].isdigit():
                num = num * 10 + int(tokens[i])
                i += 1
            vals.append(num)
            continue

        if tokens[i] == '(':
            ops.append('(')
        elif tokens[i] == ')':
            while ops[-1] != '(':
                apply_op(ops, vals)
            ops.pop()  # remove '('
        else:
            while ops and ops[-1] != '(' and precedence(ops[-1]) >= precedence(tokens[i]):
                apply_op(ops, vals)
            ops.append(tokens[i])
        i += 1

    while ops:
        apply_op(ops, vals)

    return vals[0]

Infix to Postfix (Shunting Yard)

Infix:    3 + 4 * 2 / (1 - 5)
Postfix:  3 4 2 * 1 5 - / +

Both functions below take a token list, not a raw string, so tokenize first. Classify each token by asking “is it an operator?” — not by its Python type. '-11' is a negative number but '-' is an operator, and a type test cannot tell them apart once input arrives as strings (which is exactly how LeetCode hands it to you).

PREC = {'+': 1, '-': 1, '*': 2, '/': 2}

def tokenize(s):
    """'3 + 4 * 2 / (1 - 5)' -> [3, '+', 4, '*', 2, '/', '(', 1, '-', 5, ')']"""
    out, num = [], ''
    for ch in s:
        if ch.isdigit():
            num += ch
            continue
        if num:
            out.append(int(num)); num = ''
        if ch in PREC or ch in '()':
            out.append(ch)
    if num:
        out.append(int(num))
    return out

def infix_to_postfix(tokens):
    output, ops = [], []

    for token in tokens:
        if token in PREC:
            # Pop every operator that binds at least as tightly — that is what
            # makes equal precedence associate left-to-right.
            while ops and ops[-1] != '(' and PREC[ops[-1]] >= PREC[token]:
                output.append(ops.pop())
            ops.append(token)
        elif token == '(':
            ops.append(token)
        elif token == ')':
            while ops[-1] != '(':
                output.append(ops.pop())
            ops.pop()                      # discard the matching '('
        else:
            output.append(token)           # a number

    while ops:
        output.append(ops.pop())

    return output

infix_to_postfix(tokenize("3 + 4 * 2 / (1 - 5)")) gives [3, 4, 2, '*', 1, 5, '-', '/', '+'] — the postfix line shown above.

Postfix Evaluation

def eval_postfix(tokens):
    """LC 150. Accepts ints or strings: [2, 1, '+'] and ['2', '1', '+'] both work."""
    stack = []
    for token in tokens:
        if token in PREC:                    # operator, not a number
            b, a = stack.pop(), stack.pop()  # NOTE: b is the *right* operand
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            else: stack.append(int(a / b))   # int() truncates toward zero, // floors
        else:
            stack.append(int(token))         # int('-11') == -11, so negatives are fine
    return stack[0]

Why pop order matters. b comes off first because it was pushed last, so it is the right operand. Writing a, b = stack.pop(), stack.pop() silently computes 5 - 3 as 3 - 5; the bug is invisible for + and * and only shows up on - and /.

Walkthrough — LC 227: Basic Calculator II

This template solves: LC 227, 224 (with parens), 772 (full), 150 (postfix / RPN).

Full statement. Evaluate a string arithmetic expression with + - * /, non-negative integers, and spaces — no parentheses. Integer division truncates toward zero. "3+2*2" → 7; "3/2" → 1; "3+5 / 2" → 5.

Pattern-focused solution. The two-stack shunting-yard evaluator in §4 handles full precedence with parentheses — but for the no-paren case it is overkill. The lean idiom is a single stack of signed terms: buffer the current number with the pending operator. +/- push the number (negated for -) as a deferred term; *// are higher precedence so resolve them immediately against the stack top. The answer is the sum of the stack at the end — addition is order-free, so no second stack is needed.

def calculate(s):
    stack = []
    num, op = 0, '+'                    # op = operator PENDING before num
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if ch in '+-*/' or i == len(s) - 1:   # flush at each op and at the end
            if op == '+':   stack.append(num)
            elif op == '-': stack.append(-num)
            elif op == '*': stack.append(stack.pop() * num)
            elif op == '/': stack.append(int(stack.pop() / num))
            op, num = ch, 0
    return sum(stack)

Trace over "3+5 / 2" (spaces skipped, int(5/2)=2):

read 3            num=3
'+' : flush op='+' -> push 3           stack: [3]      op='+' num=0
read 5            num=5
'/' : flush op='+' -> push 5           stack: [3, 5]   op='/' num=0
read 2            num=2
end : flush op='/' -> pop 5, push 5/2=2  stack: [3, 2]

sum([3, 2]) = 5   ✓

★ Insight ─────────────────────────────────────

• Precedence becomes a “resolve now vs defer” decision. *// bind tighter than +/-, so they must consume the stack top before the next term forms; +/- can wait as signed terms and be summed at the very end. That reframing dissolves precedence into a one-pass rule — no operator stack.
• op lags one token behind num. You act on the previous operator when you hit the current one (or the string’s end) — the number is only complete once its terminator appears. Missing the i == len(s)-1 flush is the classic off-by-one that drops the last term.
• When parens enter (LC 224), fall back to the two-stack parser in §4 — the single-stack trick can’t express arbitrary nesting. Knowing which tool the constraints demand is the skill; both live in this section on purpose. ─────────────────────────────────────────────────

5. Monotonic Deque (Sliding Window Min/Max)

The queue counterpart of monotonic stack. Maintains a window’s min or max in O(1) amortized per element — each index is pushed once and popped once, so the inner while loops do O(n) work in total even though a single step can pop many entries.

Same algorithm, other entry point: Sliding Window §8 frames this as a window problem rather than a data-structure one. This section owns the amortized argument and the min/max symmetry; that one owns the window-template context.

The Core Idea

Maintain a deque of indices. The front is always the current window’s min (or max). Remove from the back when a new element makes old elements irrelevant. Remove from the front when the element leaves the window.

Sliding window max, window size k=3:

arr: [1, 3, -1, -3, 5, 3, 6, 7]

The deque holds INDICES whose values are in decreasing order,
so the front is always the current window's max.

Window [1, 3, -1]:
  3 evicts 1 from the back (1 < 3); -1 is smaller than 3, kept behind it.
  deque (indices): [1, 2]   ->   max = arr[deque[0]] = arr[1] = 3

(Full step-by-step trace over the whole array is in the Sliding Window Trace below.)

Sliding Window Maximum

from collections import deque

def max_sliding_window(arr, k):
    dq = deque()  # stores indices, values in DECREASING order
    result = []

    for i in range(len(arr)):
        # Remove elements outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove elements smaller than arr[i] from back
        # (they can never be the max while arr[i] is in the window)
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()

        dq.append(i)

        # Window is full (i >= k-1), record the max
        if i >= k - 1:
            result.append(arr[dq[0]])

    return result

Sliding Window Trace

arr = [1, 3, -1, -3, 5, 3, 6, 7],  k = 3

i=0: arr[0]=1,  dq=[0]                          (not full yet)
i=1: arr[1]=3,  pop 0 (1<3), dq=[1]             (not full yet)
i=2: arr[2]=-1, dq=[1,2]                        result: [3]   (max=arr[1]=3)
i=3: arr[3]=-3, dq=[1,2,3]                      result: [3,3] (max=arr[1]=3)
i=4: arr[4]=5,  pop 3,2,1 (all<5), dq=[4]       result: [3,3,5]
i=5: arr[5]=3,  dq=[4,5]                        result: [3,3,5,5]
i=6: arr[6]=6,  pop 5,4 (all<6), dq=[6]         result: [3,3,5,5,6]
i=7: arr[7]=7,  pop 6 (6<7), dq=[7]             result: [3,3,5,5,6,7]

Sliding Window Minimum

Flip the comparison: maintain increasing order in the deque.

from collections import deque

def min_sliding_window(arr, k):
    dq = deque()  # stores indices, values in INCREASING order
    result = []

    for i in range(len(arr)):
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        while dq and arr[dq[-1]] >= arr[i]:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(arr[dq[0]])

    return result

Why It’s O(N)

Each element is pushed into the deque once and popped at most once. Total operations: 2N. Even though there’s a while loop inside the for loop, the total work across all iterations is O(N).

Monotonic Deque vs Monotonic Stack

Walkthrough — LC 239: Sliding Window Maximum

This exact template solves LC 239. Three neighbours use the same monotonic-deque tool but each reshapes it, so treat them as variations to derive rather than copy targets: LC 1425 (constrained subsequence sum) runs a max-deque over DP values instead of raw array values; LC 862 (shortest subarray ≥ K) runs an increasing deque over prefix sums with a variable window, and is worked in full at Sliding Window §13; LC 1438 (abs-diff window) needs two deques at once, a max and a min, to track the window’s spread.

Full statement. Given nums and window size k, return the maximum of every contiguous window of size k as the window slides left to right by one each step. nums=[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7].

Pattern-focused solution. A max-heap gives O(n log k); the deque gives O(n). Maintain indices in a deque whose values are strictly decreasing, so the front is always the window’s max. Two evictions per step: from the back, drop any index whose value ≤ nums[i] (a smaller-or-equal element behind a newer bigger one can never be the max again — dominated); from the front, drop the index if it has slid out of the window (< i-k+1). This is the exact max_sliding_window from §5 — the walkthrough just narrates why each pop is safe.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()            # indices, nums[...] strictly DECREASING
    result = []
    for i in range(len(nums)):
        while dq and dq[0] < i - k + 1:      # front expired?
            dq.popleft()
        while dq and nums[dq[-1]] <= nums[i]: # back dominated?
            dq.pop()
        dq.append(i)
        if i >= k - 1:                        # first full window
            result.append(nums[dq[0]])        # front = current max
    return result

Trace over nums=[1,3,-1,-3,5,3,6,7], k=3:

i=0 v=1 : dq=[0]                                   (window not full)
i=1 v=3 : pop 0 (1<=3), dq=[1]                      (not full)
i=2 v=-1: dq=[1,2]                    result:[3]    max=nums[1]=3
i=3 v=-3: dq=[1,2,3]                  result:[3,3]  max=nums[1]=3
i=4 v=5 : pop 3,2,1 (all<=5), dq=[4]  result:[3,3,5]
i=5 v=3 : dq=[4,5]                    result:[3,3,5,5]
i=6 v=6 : pop 5,4 (all<=6), dq=[6]    result:[3,3,5,5,6]
i=7 v=7 : pop 6 (6<=7), dq=[7]        result:[3,3,5,5,6,7]   ✓

★ Insight ─────────────────────────────────────

• A smaller element that arrives later makes every smaller-or-equal earlier element dead weight. While the new, bigger element is in the window, none of them can ever be the max — so evict them permanently. That “dominated ⇒ never relevant again” is what lets each index be popped at most once (the O(N) guarantee).
• Order the two evictions front-then-back, and evict before reading the answer. If you read dq[0] before dropping the expired front, you report a max from outside the window — the single most common bug (called out in §5’s pitfalls). The window is only valid once both pops are done.
• A stack answers “unbounded history” (all earlier elements); a deque answers “last k”. The moment a problem bounds how far back you may look, you need the extra front-eviction — hence the deque. This is the litmus test for deque-vs-stack. ─────────────────────────────────────────────────

6. Histogram Problems

Largest Rectangle in Histogram

Problem: Given bars of varying heights, find the largest rectangular area.

Heights: [2, 1, 5, 6, 2, 3]

     _
    | |
  _ | |
 | || |   _
 | || | _ | |
_| || || || |
|_||_||_||_||_|
 2  1  5  6  2  3

Largest rectangle: 5x2 = 10 (bars of height 5 and 6)

Key insight: For each bar, find how far it can extend left and right (i.e., the nearest shorter bar on each side). This is exactly previous smaller + next smaller.

def largest_rectangle_histogram(heights):
    n = len(heights)
    stack = []  # monotonic increasing stack of indices
    max_area = 0

    for i in range(n + 1):
        h = heights[i] if i < n else 0  # sentinel: force empty the stack

        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # width: from (stack top + 1) to (i - 1)
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)

        stack.append(i)

    return max_area

Trace

heights = [2, 1, 5, 6, 2, 3]

i=0: h=2, push          stack: [0]
i=1: h=1, pop 0 (h=2)   area = 2*1 = 2     stack: [1]
i=2: h=5, push           stack: [1, 2]
i=3: h=6, push           stack: [1, 2, 3]
i=4: h=2, pop 3 (h=6)    area = 6*1 = 6
          pop 2 (h=5)    area = 5*2 = 10    stack: [1, 4]
i=5: h=3, push           stack: [1, 4, 5]
i=6: h=0 (sentinel)
     pop 5 (h=3)    area = 3*1 = 3
     pop 4 (h=2)    area = 2*4 = 8
     pop 1 (h=1)    area = 1*6 = 6

Max area = 10

Why Width Calculation Works

When we pop index j because of index i:

• i is the next smaller on the right
• stack[-1] (after pop) is the previous smaller on the left
• Width = i - stack[-1] - 1 (everything between the two boundaries)

heights:   ... [3] [5] [6] [2] ...
indices:   ...  a   j        i  ...

Pop j (height 5) because of i (height 2):
  Left boundary: a (previous smaller)
  Right boundary: i (next smaller)
  Width = i - a - 1

Maximal Rectangle in Binary Matrix

Problem: Find the largest rectangle of 1s in a binary matrix.

Reduction: Treat each row as the base of a histogram. Build up heights row by row, apply histogram algorithm.

def maximal_rectangle(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    heights = [0] * n
    max_area = 0

    for i in range(m):
        for j in range(n):
            # int() so this works whether the cell is 1 or "1" — LC 85 hands you
            # STRINGS, and `matrix[i][j] == 1` would be False for every cell,
            # silently returning 0 instead of crashing.
            heights[j] = heights[j] + 1 if int(matrix[i][j]) else 0

        max_area = max(max_area, largest_rectangle_histogram(heights))

    return max_area

The column-height recurrence is the whole trick. heights[j] counts consecutive 1s ending at row i, so a 0 must reset it to 0 rather than decrement it — a rectangle cannot span a hole. Every row then becomes a histogram whose largest rectangle you already know how to find, and the answer is the best over all rows.

Matrix:         Heights row by row:
1 0 1 0 0       [1, 0, 1, 0, 0]  -> max rect = 1
1 0 1 1 1       [2, 0, 2, 1, 1]  -> max rect = 3
1 1 1 1 1       [3, 1, 3, 2, 2]  -> max rect = 6
1 0 0 1 0       [4, 0, 0, 3, 0]  -> max rect = 3

Answer: 6 (3x2 block in row 3)

Walkthrough — LC 84: Largest Rectangle in Histogram

This template solves: LC 84, 85 (maximal rectangle), 1504 (submatrices with all ones), 42 (rain water — the mirror).

Full statement. Given heights[] where heights[i] is the height of the i-th bar (width 1), find the area of the largest axis-aligned rectangle that fits inside the histogram. heights=[2,1,5,6,2,3] → 10 (bars 5 and 6 give height 2 over width… no — bars of height 5,6 span width 2 at height 5 = 10).

Pattern-focused solution. For a bar of height h to be the limiting height of a rectangle, extend left and right until you hit a strictly shorter bar on each side. So every bar needs its previous-smaller and next-smaller — two monotonic-stack facts. The elegant single-pass version fuses them: keep an increasing stack of indices; when bar i is shorter than the top, that top has just found its next-smaller (i), and the new stack top is its previous-smaller — enough to fix the width instantly. A trailing sentinel height 0 flushes every remaining bar. This is largest_rectangle_histogram from §6.

def largest_rectangle_histogram(heights):
    n = len(heights)
    stack = []            # increasing stack of indices
    max_area = 0
    for i in range(n + 1):
        h = heights[i] if i < n else 0        # sentinel forces full flush
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Trace over heights=[2,1,5,6,2,3]:

i=0 h=2: push               stack:[0]
i=1 h=1: 2>1 pop 0, w=1, area=2*1=2   stack:[]  push 1  stack:[1]
i=2 h=5: push               stack:[1,2]
i=3 h=6: push               stack:[1,2,3]
i=4 h=2: 6>2 pop 3, w=4-2-1=1, area=6*1=6
         5>2 pop 2, w=4-1-1=2, area=5*2=10   <- winner
         push 4             stack:[1,4]
i=5 h=3: push               stack:[1,4,5]
i=6 h=0: 3>0 pop 5, w=6-4-1=1, area=3*1=3
         2>0 pop 4, w=6-1-1=4, area=2*4=8
         1>0 pop 1, w=6,       area=1*6=6

max_area = 10   ✓

★ Insight ─────────────────────────────────────

• The width formula i - stack[-1] - 1 is “next-smaller minus previous-smaller minus one”. When you pop bar j: i is its next-smaller (right wall), and the new top after popping is its previous-smaller (left wall). The whole gap between the two walls is where bar j’s height fits — no separate prev/next arrays needed.
• The sentinel 0 at index n is not a hack — it’s the clean way to guarantee every bar is measured. Without it, bars still on the stack at the end (a non-decreasing tail) never get popped and their rectangles are missed. A virtual shorter-than-everything bar forces the final flush.
• LC 85 (maximal rectangle in a 0/1 matrix) is this function called once per row, feeding running column-heights (reset to 0 on a 0). One Hard problem becomes “build heights + reuse §6” — the payoff of isolating the histogram engine. ─────────────────────────────────────────────────

7. Stock Span and Daily Temperatures

Stock Span

Problem: For each day, how many consecutive days before it had a price <= today’s price?

Prices:  [100, 80, 60, 70, 60, 75, 85]
Spans:   [  1,  1,  1,  2,  1,  4,  6]

Day 0 (100): only itself                            -> span 1
Day 1 (80):  80; 100>80 stop                         -> span 1
Day 2 (60):  60; 80>60 stop                          -> span 1
Day 3 (70):  70,60; 80>70 stop                       -> span 2
Day 4 (60):  60; 70>60 stop                          -> span 1
Day 5 (75):  75,60,70,60; 80>75 stop                 -> span 4
Day 6 (85):  85,75,60,70,60,80; 100>85 stop          -> span 6

This is previous greater in disguise: span = distance to the previous day with a strictly higher price.

def stock_span(prices):
    n = len(prices)
    span = [0] * n
    stack = []  # decreasing stack of indices

    for i in range(n):
        while stack and prices[stack[-1]] <= prices[i]:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)

    return span

Daily Temperatures

Problem: For each day, how many days until a warmer temperature?

This is next greater element returning the distance.

def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []  # decreasing stack of indices

    for i in range(n):
        while stack and temps[stack[-1]] < temps[i]:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result

temps:  [73, 74, 75, 71, 69, 72, 76, 73]
result: [ 1,  1,  4,  2,  1,  1,  0,  0]

Walkthrough — LC 739: Daily Temperatures

This template solves: LC 739, 496/503 (next greater), 901 (online stock span), 1019 (next greater in linked list).

Full statement. Given daily temperatures[], return answer[] where answer[i] is the number of days you must wait after day i for a warmer temperature. If none, 0. [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0].

Pattern-focused solution. “Days until warmer” is next-greater-element returning a distance instead of the value. Keep a decreasing stack of indices (warm days waiting for a warmer one). Each new day i pops every colder day it beats — and because we stored indices, the wait length is simply i - idx. This is daily_temperatures from §7, index arithmetic doing the real teaching.

def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []                       # decreasing stack of DAY INDICES
    for i in range(n):
        while stack and temps[stack[-1]] < temps[i]:
            idx = stack.pop()
            result[idx] = i - idx    # distance, not value
        stack.append(i)
    return result                    # days left on stack keep 0 (no warmer day)

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

i=0 t=73: push                       stack:[0]
i=1 t=74: 73<74 pop 0, result[0]=1   push 1  stack:[1]
i=2 t=75: 74<75 pop 1, result[1]=1   push 2  stack:[2]
i=3 t=71: 75<71? no  push 3          stack:[2,3]
i=4 t=69: 71<69? no  push 4          stack:[2,3,4]
i=5 t=72: 69<72 pop 4, result[4]=1
          71<72 pop 3, result[3]=2
          75<72? no  push 5          stack:[2,5]
i=6 t=76: 72<76 pop 5, result[5]=1
          75<76 pop 2, result[2]=4
          push 6                     stack:[6]
i=7 t=73: 76<73? no  push 7          stack:[6,7]
end: 6,7 never warmed -> result stays 0

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

★ Insight ─────────────────────────────────────

• Storing indices, not temperatures, is what makes the distance fall out for free (i - idx). Had you pushed temperatures you’d know that it warmed but not when — you’d have lost the day number. This is the concrete payoff of the “store indices” rule from the top of the guide.
• The default 0 is passive, not computed. Days still on the stack at the end never found a warmer day, so their pre-filled 0 is the answer — you never write it explicitly. Recognizing “unresolved = the default” saves a cleanup pass.
• LC 901 (Stock Span) is the mirror image: previous-greater-or-equal distance instead of next-greater. Same decreasing stack, but you read the span as you push (distance back to the stack top) rather than as you pop. Next-vs-previous is just “resolve on pop” vs “resolve on push” — see §2.3. ─────────────────────────────────────────────────

8. Queue Patterns

BFS (Breadth-First Search)

The most fundamental queue pattern. Process nodes level by level.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Level-Order Processing

When you need to process each level separately:

def bfs_by_level(graph, start):
    visited = {start}
    queue = deque([start])
    level = 0

    while queue:
        size = len(queue)  # number of nodes at current level
        for _ in range(size):
            node = queue.popleft()
            # process node at this level
            for neighbor in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        level += 1

Task Scheduling / Process Queue

from collections import deque

def round_robin(tasks, quantum):
    """Simulate round-robin CPU scheduling."""
    queue = deque(tasks)  # (task_name, remaining_time)
    time = 0
    order = []

    while queue:
        name, remaining = queue.popleft()
        run = min(quantum, remaining)
        time += run
        remaining -= run
        if remaining > 0:
            queue.append((name, remaining))
        else:
            order.append((name, time))

    return order

Recent Counter (Sliding Window with Queue)

class RecentCounter:
    """Count requests in the last 3000 ms."""
    def __init__(self):
        self.queue = deque()

    def ping(self, t):
        self.queue.append(t)
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

9. Augmented Stacks and Queues

Min Stack (O(1) getMin)

class MinStack:
    def __init__(self):
        self.stack = []     # (value, current_min)

    def push(self, val):
        curr_min = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, curr_min))

    def pop(self):
        return self.stack.pop()[0]

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

Max Stack (O(1) getMax)

Same idea: store (value, current_max) pairs.

Min Queue (O(1) amortized getMin)

Use two stacks to simulate a queue, each stack tracking its min.

class MinQueue:
    """Queue with O(1) amortized min query."""
    def __init__(self):
        self.push_stack = []   # (val, min_so_far)
        self.pop_stack = []    # (val, min_so_far)

    def enqueue(self, val):
        curr_min = min(val, self.push_stack[-1][1]) if self.push_stack else val
        self.push_stack.append((val, curr_min))

    def dequeue(self):
        if not self.pop_stack:
            while self.push_stack:
                val, _ = self.push_stack.pop()
                curr_min = min(val, self.pop_stack[-1][1]) if self.pop_stack else val
                self.pop_stack.append((val, curr_min))
        return self.pop_stack.pop()[0]

    def get_min(self):
        if self.push_stack and self.pop_stack:
            return min(self.push_stack[-1][1], self.pop_stack[-1][1])
        elif self.push_stack:
            return self.push_stack[-1][1]
        else:
            return self.pop_stack[-1][1]

Two Stacks = One Queue

The classic trick: a push stack and a pop stack. When pop stack is empty, pour all elements from push stack (reversing the order).

Enqueue 1, 2, 3:     push_stack: [1, 2, 3]    pop_stack: []
Dequeue:              push_stack: []            pop_stack: [3, 2, 1]
                      pop from pop_stack -> 1 (correct FIFO order!)

Amortized O(1) per operation: each element is moved at most once from push to pop stack.

Walkthrough — LC 155: Min Stack

This template solves: LC 155, 716 (max stack), 895 (max frequency stack), 1381 (custom stack).

Full statement. Design a stack with push, pop, top, and getMin — all in O(1). getMin returns the minimum element currently in the stack. A plain stack does push/pop/top in O(1) but getMin would be O(N).

Pattern-focused solution. The trap is thinking you need a separate min structure. Instead, carry the running minimum inside each frame: store (value, min_of_stack_up_to_here). When you push, the new frame’s min is min(val, previous_frame_min). Popping automatically restores the correct min because the previous frame already recorded its era’s minimum. getMin is just stack[-1][1].

class MinStack:
    def __init__(self):
        self.stack = []              # each entry: (value, min_so_far)
    def push(self, val):
        curr_min = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, curr_min))
    def pop(self):
        return self.stack.pop()[0]
    def top(self):
        return self.stack[-1][0]
    def getMin(self):
        return self.stack[-1][1]

Trace — push(-2), push(0), push(-3), getMin, pop, top, getMin:

push -2 : min(-2)          stack: [(-2,-2)]
push  0 : min(0,-2)=-2     stack: [(-2,-2), (0,-2)]
push -3 : min(-3,-2)=-3    stack: [(-2,-2), (0,-2), (-3,-3)]
getMin  -> stack[-1][1] = -3   ✓
pop     -> returns -3      stack: [(-2,-2), (0,-2)]
top     -> stack[-1][0] = 0    ✓
getMin  -> stack[-1][1] = -2   ✓  (min correctly "rewound" to the -3-free era)

★ Insight ─────────────────────────────────────

• Each frame owns the min of the stack at its own moment. That is why pop needs no recomputation — throwing away the top frame reveals the previous frame, which already stored the minimum of everything beneath it. The history is embedded, not recalculated.
• This “augment every element with a running aggregate” trick generalizes past min/max to any O(1)-mergeable summary (max, gcd, running-and/or). Swap min for the aggregate and the structure is unchanged — LC 716 (Max Stack) is literally min → max.
• Min Queue can’t reuse this directly — a queue removes from the far end, so the “min beneath me” invariant breaks. The fix is two augmented stacks simulating a queue (see §9 above); each stack keeps this same per-frame min, and getMin takes the min of the two tops. ─────────────────────────────────────────────────

10. Trapping Rain Water

A classic that combines multiple stack/pointer techniques.

Approach 1: Monotonic Stack

def trap_stack(height):
    stack = []  # decreasing stack of indices
    water = 0

    for i in range(len(height)):
        while stack and height[stack[-1]] < height[i]:
            bottom = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[bottom]
            water += width * bounded_height

        stack.append(i)

    return water

How It Works

height: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

When we pop index 2 (h=0) because of index 3 (h=2):
  bottom = height[2] = 0
  left wall = height[stack[-1]] = height[1] = 1
  right wall = height[3] = 2
  water level = min(1, 2) - 0 = 1
  width = 3 - 1 - 1 = 1
  water += 1 * 1 = 1

We compute water LAYER BY LAYER, horizontally.

Approach 2: Two Pointers (O(1) space)

def trap_two_pointers(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

Approach 3: Prefix Max Arrays

def trap_prefix(height):
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])

    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])

    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]

    return water

Comparison

Walkthrough — LC 42: Trapping Rain Water

This template solves: LC 42, 407 (2D rain water), 84 (histogram — the mirror), 11 (container with most water — two-pointer cousin).

Full statement. Given height[] (an elevation map, bar width 1), compute how much rain water it traps after raining. [0,1,0,2,1,0,1,3,2,1,2,1] → 6.

Pattern-focused solution. Water above position i is bounded by min(tallest wall left, tallest wall right) - height[i]. The monotonic-stack view computes water in horizontal layers: keep a decreasing stack of indices; when bar i is taller than the top, the top is a valley floor that just found its right wall (i) — the new stack top is its left wall. The trapped slab between them is width × (min(left,right) - floor). This is trap_stack from §10.

def trap_stack(height):
    stack = []                # decreasing stack of indices
    water = 0
    for i in range(len(height)):
        while stack and height[stack[-1]] < height[i]:
            bottom = stack.pop()          # valley floor
            if not stack:                 # no left wall -> water spills off
                break
            width = i - stack[-1] - 1
            bounded = min(height[i], height[stack[-1]]) - height[bottom]
            water += width * bounded
        stack.append(i)
    return water

Trace — the key layer, popping index 2 (h=0) because of index 3 (h=2) in [0,1,0,2,...]:

i=0 h=0: push               stack:[0]
i=1 h=1: 0<1 pop 0, stack empty -> break; push 1   stack:[1]
i=2 h=0: 1<0? no  push 2    stack:[1,2]
i=3 h=2: 1... wait top is 2 (h=0): 0<2 pop 2 (floor)
         left wall = stack[-1]=1 (h=1), right wall = 3 (h=2)
         width = 3-1-1 = 1
         bounded = min(1,2) - 0 = 1
         water += 1*1 = 1
         now top 1 (h=1): 1<2 pop 1, stack empty -> break
         push 3             stack:[3]
... continues; final water = 6   ✓

★ Insight ─────────────────────────────────────

• Water is filled in horizontal slabs, not vertical columns. Each pop resolves one rectangular layer bounded by a left wall, a right wall, and the valley floor being popped. This is the same “pop = fix a rectangle” move as LC 84 — trapping water and largest rectangle are the same monotonic-stack skeleton with a different area formula.
• if not stack: break is essential — a popped floor with nothing beneath it has no left wall, so water spills off that side and traps nothing. Beginners omit this and index into an empty stack.
• Two pointers beat the stack here on space (O(1) vs O(N)). The insight: whichever side has the shorter running max is the binding wall, so advance that pointer and bank side_max - height. When both a stack and a two-pointer solution exist, the two-pointer one usually wins — but the stack version generalizes to problems (like LC 84) where two pointers don’t apply. ─────────────────────────────────────────────────

11. Pattern Recognition Cheat Sheet

By Problem Type

Monotonic Stack Decision Table

Complexity Summary

The Meta-Pattern

Almost every stack/queue problem follows this template:

for each element:
    while stack/deque is not empty AND current element violates the invariant:
        pop and COMPUTE ANSWER for popped element
    push current element

The “invariant” is either increasing or decreasing order. The “answer computation” varies by problem (next greater, rectangle area, trapped water, etc.), but the structure is always the same.

Common Pitfalls

Practice Order

Start here
    │
    ▼
  20  (Easy)    ──── Valid Parentheses: plain stack matching, no monotonic invariant
    │
    ▼
  739 (Medium) ──── Daily Temperatures: monotonic stack returning distances
    │
    ▼
  503 (Medium) ──── Next Greater Element II: same stack, iterate 2N for circular
    │
    ▼
  84  (Hard)   ──── Largest Rectangle in Histogram: pop = fix a bar's width via prev/next smaller
    │
    ▼
  85  (Hard)   ──── Maximal Rectangle: stack row-histograms on top of LC 84
    │
    ▼
  42  (Hard)   ──── Trapping Rain Water: stack (layers) or two pointers — the capstone

The Stack & Queue Toolbox at a Glance

Does an element WAIT for a later element to resolve it?
│
├─ NO  ── not a stack/queue problem — heap? hash map? sort?
│
└─ YES ── which pending element resolves FIRST?
   │
   ├─ NEWEST first (nesting / nearest / innermost)  =====>  STACK
   │   │
   │   ├─ "next / prev greater or smaller"        Monotonic stack (§2)  — LC 496, 739
   │   ├─ "matching / balanced brackets"          Stack match     (§3)  — LC 20
   │   ├─ "evaluate expression"                   Stack parser    (§4)  — LC 227
   │   ├─ "largest rectangle / max area"          Increasing stack(§6)  — LC 84
   │   ├─ "trapped water between walls"           Decreasing stack(§10) — LC 42
   │   └─ "min/max with push/pop in O(1)"         Augmented stack (§9)  — LC 155
   │
   └─ OLDEST first (arrival / level / time order) =====>  QUEUE / DEQUE
       │
       ├─ "max/min over a window of size k"        Monotonic deque (§5)  — LC 239
       ├─ "shortest hops / level by level"         BFS queue       (§8)  — LC 102
       └─ "count events in a time window"          Plain queue     (§8)  — LC 933

THREE MOVES, EVERY MONOTONIC PROBLEM

1. PUSH the index (never the value) — it now waits for its trigger.
2. POP while the new element breaks the invariant — the pop BIRTHS an answer.
3. READ the answer at the pop (next-*) or at the push (prev-*).

LeetCode Practice Ladder (the 8 walkthroughs)

20  Valid Parentheses        pure LIFO matching — no invariant
  │
155 Min Stack                augment each frame with a running min
  │
739 Daily Temperatures       monotonic stack returning a DISTANCE
  │
496 Next Greater Element I   monotonic stack + hash-map lookup
  │
227 Basic Calculator II      single stack of signed terms, precedence = resolve-now
  │
239 Sliding Window Maximum   monotonic DEQUE — evict front (expired) + back (dominated)
  │
84  Largest Rectangle        pop = fix a bar's width via prev/next smaller
  │
42  Trapping Rain Water      pop = fill a horizontal layer — the capstone

When This Fails

A monotonic stack answers “nearest element to my left/right that is greater/smaller”. It is the wrong tool when:

• You need the extreme of an arbitrary set, not the nearest unresolved neighbour. That is a heap. The stack only ever knows about elements it has not yet resolved.
• You need the extreme of a sliding window. A stack cannot expire elements from the far end; use a monotonic deque (§5).
• Elements must be removed from the middle. Neither structure supports it. Use a balanced BST or an order-statistic structure.
• The nesting is not actually LIFO. Interleaved bracket types like ([)] are invalid precisely because bracket matching is LIFO; if your problem allows interleaving, a stack does not model it.

Also watch the direction: scanning left-to-right with a decreasing stack gives next greater to the right. Get the direction or the strictness backwards and the code runs fine and answers a different question.

Self-Test

Answer these from memory, out loud or on paper, before looking. Recognition is not recall: rereading an explanation feels like knowing, and it is not. A question you cannot answer cold names the exact section to revisit — you do not need to reread the guide.

1. Why is a monotonic stack O(n) when it contains a nested while loop?

2. Strict (>) or non-strict (>=) when popping — how do you decide?

3. What does the stack physically hold, and why is it usually indices rather than values?

4. In the largest-rectangle-in-histogram algorithm, what does popping an element mean?

5. Why do histogram solutions append a sentinel of height 0?

6. A monotonic deque for window maximum pops from both ends. What are the two rules and why do they differ?

7. How do two stacks implement a queue in amortized O(1)?

8. Trapping rain water and largest rectangle use the same skeleton. What differs?

See Also

• Sliding Window §8 — the same monotonic deque as §5, framed as a window problem instead of a data-structure one.
• Contribution Counting §3 — the payoff of §2: once each element’s span is known, “sum of subarray minimums” becomes arithmetic.
• Prefix Sum — the prefix-max/suffix-max approach to trapping rain water (§10), and the prefix array that turns “shortest subarray with sum >= k” into a deque problem.
• Graph Patterns §1 — where the BFS queue of §8 actually earns its keep.
• Heap / Priority Queue — when you need the extreme of the whole set rather than the nearest unresolved neighbour.
• Pattern Decision Map — the router: which technique does a cold problem call for?
• Pattern Mastery Program — the spaced-repetition schedule, mastery checklist, and drill formats that turn reading into recall.

Pattern mastered — stop rescanning for the nearest neighbor and let each element wait on the stack until the one that resolves it walks by.