CODING PATTERNS · LESSON 18 OF 28 · 62 MIN VIDEO · 20 PROBLEMS

Stacks

Module Progress (0 / 20 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (62 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Stacks — How the Pattern Works

A stack is a Last-In, First-Out (LIFO) data structure that maintains unresolved elements, open nesting scopes, or monotonically ordered candidates so only the newest active item (stack[-1]) interacts with each incoming token. By preserving the invariant that stack[-1] always holds the innermost open delimiter, most recent surviving neighbor, or nearest unresolved element, a stack eliminates repeated full-input rescans and nested lookahead loops. Because every element or index is pushed onto the stack at most once and popped at most once, multi-pass O(n^2) (or exponential) brute-force algorithms collapse into O(n) amortized time.

WHEN TO USE THIS PATTERN
  • Nested or paired delimiters and hierarchical intervals—such as brackets ()[]{}, call-stack start/end logs, or k[text] blocks—where the most recently opened scope must close or pause/resume first.
  • Cascading adjacent deletions or undo actions—such as removing duplicate pairs, deleting k-length character runs, or resolving ".." in Unix paths—where removing elements exposes new interactions at the join boundary.
  • Expression parsing with parentheses or operator precedence (+, -, *, /, boolean !/&/|), where lower-precedence terms or outer scopes wait on the stack while higher-precedence or inner operations resolve immediately.
  • Nearest greater/smaller element queries, line-of-sight visibility, ramp width maximization, or lexicographically smallest subsequences, where a monotonic stack maintains sorted unresolved candidates.
  • Lazy recursive unpacking or LIFO-to-FIFO structural adapters, such as flattening nested lists on demand (next() / has_next()) or implementing a queue in O(1) amortized time with two stacks.
COMMON INTERVIEW PITFALLS
  • Accessing stack[-1] or calling stack.pop() without guarding if stack:—inputs starting with a closing delimiter ')' or navigating ".." at root "/" will raise IndexError.
  • Forgetting leftover state after the scan terminates, such as unclosed '(' indices still sitting on stack in parenthesis validation/removal or the final accumulated num at the end of Basic Calculator / Basic Calculator II.
  • Using Python floor division // instead of truncation toward zero int(a / b) for signed integer division (-3 // 2 evaluates to -2, whereas int(-3 / 2) truncates toward zero to -1).
  • Using strict < instead of <= (or > instead of >=) in monotonic stack while conditions when duplicate values exist, or pushing values instead of indices when index distances (i - j) are needed.
Matching & Adjacent Cancellation StackApply when validating paired delimiters, cancelling adjacent duplicates/substrings, or handling undo tokens where an incoming element only interacts with the latest surviving element.
def process_cancellation(seq, cancels):
    stack = []
    for item in seq:
        if stack and cancels(stack[-1], item):
            stack.pop()
        else:
            stack.append(item)
    return stack
Nested Scope / State Suspension StackApply when opening brackets suspend an active outer computation (running sum, sign, multiplier, or operator) and closing brackets fold the completed inner result back into the saved outer state.
def evaluate_nested(tokens, init_state, combine, step):
    stack, state = [], init_state
    for tok in tokens:
        if tok == "(":
            stack.append(state)
            state = init_state
        elif tok == ")":
            state = combine(stack.pop(), state)
        else:
            state = step(state, tok)
    return state
Monotonic Stack (Next Greater Element)Apply when each element seeks its next greater/smaller neighbor, visibility count, or valid subarray boundary; maintaining sorted unresolved indices lets each incoming value resolve all dominated stack tops in O(1) amortized time.
def next_greater_indices(nums):
    res = [-1] * len(nums)
    stack = []  # indices with monotonically non-increasing nums[idx]
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = i
        stack.append(i)
    return res
🔒 PRO PROBLEMTarget: O(n) time · O(n) space

10. Number of Valid Subarrays

Pattern Trigger: runs end at the first smaller value → stack

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

We push one, then two, then three. Then we pop twice. What's on top now?