Skip to main content

Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

Stack Pattern

​
What is Stack?

Stack is a LIFO (Last In, First Out) data structure where elements are added and removed from the same end — the top. Think of it like a spring-loaded plate dispenser in a cafeteria: you can only take the top plate, and when a new plate is added, it goes on top. You never reach into the middle. That constraint — only the most recent item is accessible — is exactly what makes stacks powerful for problems that care about recency and nesting. In algorithm problems, stacks appear in three major families: matching problems (parentheses, tags, nested structures), expression evaluation (calculators, compilers), and monotonic stack problems (next greater/smaller element, histograms). The key insight is always the same: when the “most recently seen” item determines what happens next, a stack is the right tool. Key operations and their complexity:
  • push (add to top): O(1)
  • pop (remove from top): O(1)
  • peek/top (view top without removing): O(1)
Common pitfall in practice: In Python, list works perfectly as a stack (append and pop are both O(1)). But in Java, prefer ArrayDeque over Stack — the Stack class is synchronized and inherits from Vector, adding unnecessary overhead. The Java docs themselves recommend Deque as a replacement.
Quick Recognition: Problems involving matching pairs, nested structures, “previous/next greater element”, or undo operations. If you need to track “the most recent unresolved thing,” reach for a stack.

​
Pattern Recognition Cheatsheet

These exact problem-statement keywords should make you reach for a stack within 30 seconds of reading. Build the mental reflex once and you will solve most stack problems before the interviewer finishes explaining them.
Keyword / Shape in ProblemStack Variant to Use
”matching parens”, “balanced brackets”, “valid HTML/XML tags”Push openers, pop on closer, match types
”next greater element”, “next smaller”, “first warmer day”Monotonic stack of indices
”evaluate expression”, “calculator”, “RPN”, “infix”Operand stack (or two stacks for operators)
“decode string”, “nested encoding”, “k[ab]“Stack of (prev_string, repeat_count) tuples
”undo / redo”, “browser back”, “history”Two stacks (action plus inverse)
“simplify path”, “canonical path”, ”/.. /.”Push directories, pop on ..
”asteroid collision”, “remove adjacent duplicates”Push, pop on collision rule
”min stack” / “max stack” with O(1) queryAuxiliary stack of running min or max
”largest rectangle in histogram”, “trap rain water”Monotonic increasing or decreasing stack
”stock span”, “previous greater day”Monotonic decreasing stack of (price, span)
“the most recent X that…”Plain LIFO stack of candidates
Rule of thumb: if the problem talks about recency (“most recent unresolved…”) or nesting (“inside the inner…”), it is a stack. If it talks about order of arrival (“first one in…”) it is a queue. If it talks about the next/previous element with property P, it is a monotonic stack.

​
Reusable Template Code

Three skeletons cover the vast majority of stack problems. Internalize them and you will write each one in under a minute under interview pressure. 
# Skeleton 1: Matching / balanced brackets
def matching_brackets(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs.values():            # opener
            stack.append(c)
        elif c in pairs:                   # closer
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack                       # all openers must be closed

# Skeleton 2: Monotonic stack (next greater / smaller)
def monotonic_next_greater(nums):
    result = [-1] * len(nums)
    stack = []                             # stores INDICES, not values
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x        # pop's "next greater" is current
        stack.append(i)
    return result

# Skeleton 3: Save-and-restore context (Calculator, Decode String)
def context_stack(s):
    stack = []
    state = initial_state()
    for c in s:
        if opens_new_context(c):
            stack.append(state)            # snapshot outer context
            state = initial_state()        # reset for inner work
        elif closes_context(c):
            outer = stack.pop()
            state = combine(outer, state)  # merge inner result into outer
        else:
            state = update(state, c)
    return state
Java specific: never use java.util.Stack. It extends Vector and is synchronized — meaning every push and pop takes a lock you do not need. Use Deque<T> with ArrayDeque<>() as the implementation. The Java docs themselves recommend this. The Stack class exists only for legacy compatibility.

​
Pattern Recognition Checklist

Use Stack When

  • Matching parentheses/brackets/tags
  • Evaluating expressions (postfix/infix)
  • Finding next/previous greater/smaller
  • Processing nested structures
  • Implementing undo/back operations

Don't Use When

  • Need random access to elements
  • FIFO ordering needed (use Queue)
  • Need to process from both ends
  • Simple array traversal suffices

​
Stack Type Quick Reference

Problem TypeStack TypeDirection
Next Greater ElementMonotonic DecreasingLeft to Right
Previous Greater ElementMonotonic DecreasingLeft to Right
Next Smaller ElementMonotonic IncreasingLeft to Right
Largest RectangleMonotonic IncreasingLeft to Right
Trapping Rain WaterEitherTwo-pointer or stack

​
When to Use

Matching Problems

Parentheses, tags, nested structures

Expression Evaluation

Infix, postfix, prefix expressions

Monotonic Stack

Next greater/smaller element

Undo Operations

Browser history, text editors

​
Pattern Variations

​
1. Valid Parentheses

The classic stack problem. The core insight: the most recently opened bracket must be the first one closed. That is exactly LIFO ordering. A counter alone cannot solve this for multiple bracket types — ([)] has balanced counts but invalid nesting. Only a stack tracks the order of opens. Complexity: O(n) time, O(n) space in the worst case (all opening brackets). Edge cases: Empty string (valid), single character (always invalid), only opening brackets (stack leftover — invalid), only closing brackets (empty stack check catches it). 
def is_valid(s):
    """Check if parentheses are balanced and properly nested.
    
    Walkthrough with '({[]})':
      char='(' -> push '('.           stack=['(']
      char='{' -> push '{'.           stack=['(', '{']
      char='[' -> push '['.           stack=['(', '{', '[']
      char=']' -> top='[' matches.    stack=['(', '{']
      char='}' -> top='{' matches.    stack=['(']
      char=')' -> top='(' matches.    stack=[]
    Stack empty -> valid!
    """
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in mapping:  # Closing bracket
            if not stack or stack[-1] != mapping[char]:
                return False  # Mismatch or no matching opener
            stack.pop()
        else:  # Opening bracket
            stack.append(char)
    
    return len(stack) == 0  # Leftover openers = invalid

​
2. Decode String

This problem extends the matching pattern by storing context (the accumulated string and its repeat count) on the stack. Think of it like nested function calls: each [ opens a new scope with its own local variables. On ], you return the result to the caller scope. Complexity: O(output_length) time — the output can be exponentially larger than the input (e.g., 10[10[10[a]]] produces 1000 characters from ~15 input characters). Edge case: Multi-digit numbers like 12[a] — you must build the number digit by digit with current_num = current_num * 10 + int(char). 
def decode_string(s):
    """Decode strings like '3[a2[c]]' -> 'accaccacc'
    
    Walkthrough with '3[a2[c]]':
      '3' -> current_num = 3
      '[' -> push ("", 3), reset: current_str="", current_num=0
      'a' -> current_str = "a"
      '2' -> current_num = 2
      '[' -> push ("a", 2), reset: current_str="", current_num=0
      'c' -> current_str = "c"
      ']' -> pop ("a", 2): current_str = "a" + "c"*2 = "acc"
      ']' -> pop ("", 3): current_str = "" + "acc"*3 = "accaccacc"
    """
    stack = []
    current_num = 0
    current_str = ""
    
    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif char == ']':
            prev_str, num = stack.pop()
            current_str = prev_str + current_str * num
        else:
            current_str += char
    
    return current_str

​
3. Basic Calculator

The stack acts as a context saver here. On (, you pause the outer evaluation by pushing the running result and current sign, then start fresh inside the parentheses. On ), you merge the inner result back into the outer context. This is exactly how call stacks work in programming languages — every function call saves the caller’s state, and every return restores it. Complexity: O(n) time, O(d) space where d is the maximum nesting depth. Edge cases: Leading minus sign (e.g., "-1+2"), spaces between characters, deeply nested expressions like ((((1+2)))). 
def calculate(s):
    """Evaluate expression with +, -, (, ).
    
    Walkthrough with '1 - (2 + 3)':
      '1' -> number=1
      '-' -> result=1, sign=-1, number=0
      '(' -> push (1, -1), result=0, sign=1
      '2' -> number=2
      '+' -> result=2, sign=1, number=0
      '3' -> number=3
      ')' -> result=2+1*3=5. Pop: result = 5*(-1) + 1 = -4
    Result: -4
    """
    stack = []
    result = 0
    number = 0
    sign = 1
    
    for char in s:
        if char.isdigit():
            number = number * 10 + int(char)
        elif char == '+':
            result += sign * number
            number = 0
            sign = 1
        elif char == '-':
            result += sign * number
            number = 0
            sign = -1
        elif char == '(':
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif char == ')':
            result += sign * number
            number = 0
            result *= stack.pop()  # sign
            result += stack.pop()  # previous result
    
    return result + sign * number

​
4. Min Stack

The key insight: a single stack cannot give O(1) minimum because popping might change the min, and you would need to scan. The fix is a second “min stack” that mirrors the main stack’s minimum at every height. The space-time trade-off is the core of this problem. Critical detail: Push to the min stack when val <= min_stack[-1], NOT when val < min_stack[-1]. The <= handles duplicate minimums. Without it, popping one copy of the minimum incorrectly removes it from the min stack while another copy still exists on the main stack. Complexity: O(1) for all operations. O(n) extra space in the worst case (strictly decreasing input fills both stacks equally). 
class MinStack:
    """Stack that supports O(1) getMin().
    
    Example sequence:
      push(3) -> stack=[3], min_stack=[3]
      push(1) -> stack=[3,1], min_stack=[3,1]  (1 <= 3)
      push(1) -> stack=[3,1,1], min_stack=[3,1,1]  (1 <= 1, crucial!)
      pop()   -> stack=[3,1], min_stack=[3,1]  (popped 1 == min top 1)
      getMin() -> 1  (correct! would be wrong with < instead of <=)
    """
    
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self):
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        return self.stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def getMin(self):
        return self.min_stack[-1]

​
5. Daily Temperatures (Monotonic Stack)

A direct application of the “next greater element” pattern. The stack holds indices of days still “waiting” for a warmer day. When a warmer day arrives, it resolves all waiting days that are cooler — each popped element records the distance (index difference) to the warmer day. Think of the stack as a waiting room: days sit there until someone warmer shows up, then they leave and never come back. Complexity: O(n) time (each element is pushed and popped at most once — amortized O(1) per element). O(n) space for the stack. Interview tip: Always store indices on the stack, not values. You need the index for the distance calculation (i - idx), and you can always look up the value via temperatures[idx]. 
def daily_temperatures(temperatures):
    """Days until warmer temperature for each day.
    
    Walkthrough with [73, 74, 75, 71, 69, 72, 76, 73]:
      i=0: stack=[]     -> push 0.                  stack=[0]
      i=1: 74>73        -> pop 0, result[0]=1-0=1.  stack=[1]
      i=2: 75>74        -> pop 1, result[1]=2-1=1.  stack=[2]
      i=3: 71<75        -> push 3.                  stack=[2,3]
      i=4: 69<71        -> push 4.                  stack=[2,3,4]
      i=5: 72>69,72>71  -> pop 4(5-4=1), pop 3(5-3=2). stack=[2,5]
      i=6: 76>72,76>75  -> pop 5(6-5=1), pop 2(6-2=4). stack=[6]
      i=7: 73<76        -> push 7.                  stack=[6,7]
    Remaining in stack -> result stays 0.
    Result: [1, 1, 4, 2, 1, 1, 0, 0]
    """
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices of temperatures waiting for warmer day
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            result[prev_idx] = i - prev_idx
        stack.append(i)
    
    return result

​
Classic Problems

Pattern: Push opening, pop and match closingKey: Stack should be empty at end for valid input
Pattern: Monotonic increasing stackKey: Pop and calculate area when current bar is shorter
Pattern: Push numbers, pop two on operatorKey: Order matters for subtraction/division
Pattern: Split by ’/’, stack for directory navigationKey: ’..’ pops, ’.’ and ” are ignored

​
Monotonic Stack Deep Dive

The monotonic stack is one of the most powerful — and most misunderstood — patterns. The core principle: maintain elements on the stack in sorted order, and extract answers at the moment you pop. Every element is pushed exactly once and popped at most once, giving O(n) amortized time even though the code has a while-loop inside a for-loop. Decision guide: Use a monotonic decreasing stack when searching for the “next greater” element. Use a monotonic increasing stack when searching for the “next smaller” element or computing areas in histograms. The rule: the stack direction is opposite to what you are searching for. 
def next_greater_element(nums):
    """For each element, find the first element to its right that is larger.
    Return -1 if no such element exists.
    
    Walkthrough with [4, 2, 1, 3, 5]:
      i=0: stack=[]    -> push 0.                           stack=[0]
      i=1: 2<4         -> push 1.                           stack=[0,1]
      i=2: 1<2         -> push 2.                           stack=[0,1,2]
      i=3: 3>1         -> pop 2, result[2]=3.               stack=[0,1]
           3>2         -> pop 1, result[1]=3.               stack=[0]
           3<4         -> push 3.                           stack=[0,3]
      i=4: 5>3         -> pop 3, result[3]=5.               stack=[0]
           5>4         -> pop 0, result[0]=5.               stack=[]
           push 4.                                          stack=[4]
    Remaining -> result[4]=-1.
    Result: [5, 3, 3, 5, -1]
    """
    result = [-1] * len(nums)
    stack = []  # Indices of elements waiting for their next greater

    for i in range(len(nums)):
        # Pop all elements smaller than current -- they just found their answer
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]  # Current element is the "next greater"
        stack.append(i)
    
    # Anything still on the stack has no next greater element (stays -1)
    return result

def largest_rectangle_histogram(heights):
    """Find largest rectangle in histogram.
    
    Key insight: for each bar, find how far left and right it can extend
    as the shortest bar. A sentinel value (0) appended at the end forces
    all remaining bars to be popped, eliminating the need for cleanup code.
    
    Walkthrough with [2, 1, 5, 6, 2, 3]:
      After appending sentinel: [2, 1, 5, 6, 2, 3, 0]
      i=0: push 0.                                    stack=[0]
      i=1: 1<2 -> pop 0: h=2, w=1 (empty stack), area=2. stack=[1]
      i=2: push 2.                                    stack=[1,2]
      i=3: push 3.                                    stack=[1,2,3]
      i=4: 2<6 -> pop 3: h=6, w=4-2-1=1, area=6.     stack=[1,2]
           2<5 -> pop 2: h=5, w=4-1-1=2, area=10.     stack=[1]
           push 4.                                     stack=[1,4]
      i=5: push 5.                                    stack=[1,4,5]
      i=6: 0<3 -> pop 5: h=3, w=6-4-1=1, area=3.     stack=[1,4]
           0<2 -> pop 4: h=2, w=6-1-1=4, area=8.      stack=[1]
           0<1 -> pop 1: h=1, w=6 (empty), area=6.    stack=[]
    max_area = 10 (height=5, spanning indices 2-3)
    """
    stack = []  # Monotonic increasing stack of indices
    max_area = 0
    heights.append(0)  # Sentinel forces all bars to pop at the end
    
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # Width: everything between new top and current index was taller
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    
    return max_area

​
Worked LeetCode Problems: Brute Force vs Optimized

Five canonical problems cover the entire stack interview surface. For each, name the brute force first, then pivot to the stack solution. Interviewers love hearing the trade-off out loud.

​
LC 20: Valid Parentheses (Easy)

Problem. Given a string containing only ()[]{}, determine if it is valid — every opener has a matching closer in the right order. Brute force (O(n^2)). Repeatedly scan and remove inner matched pairs ((), [], {}) until nothing changes. Slow and ugly. Optimized stack (O(n) time, O(n) space). Push openers; on a closer, the stack top must be the matching opener. Empty stack at the end means valid. 
def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
        else:
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack
Why a stack and not a counter? A counter passes balanced-but-misnested cases like ([)]. Only a stack tracks the order of opens.

​
LC 155: Min Stack (Medium)

Problem. Design a stack that supports push, pop, top, and getMin, all in O(1). Brute force. Scan the whole stack on getMin — O(n) per call. Fails the constraint. Optimized — auxiliary min stack. Maintain a parallel stack whose top is always the current minimum. Push to the aux stack only when the new value is <= the current min (the <= is critical for handling duplicate minimums). 
class MinStack:
    def __init__(self):
        self.s, self.mins = [], []
    def push(self, x):
        self.s.append(x)
        if not self.mins or x <= self.mins[-1]:    # <= handles duplicate min
            self.mins.append(x)
    def pop(self):
        if self.s.pop() == self.mins[-1]:
            self.mins.pop()
    def top(self):    return self.s[-1]
    def getMin(self): return self.mins[-1]
The <= trap. With strict <, pushing [2, 0, 0] and popping the first 0 removes it from the min stack. Now getMin() returns 2 even though a 0 is still on the main stack. The interviewer is testing whether you spot this.

​
LC 224: Basic Calculator (Hard)

Problem. Evaluate an expression containing +, -, (, ) and integers. Brute force. Convert infix to RPN with shunting-yard, then evaluate. Works but is overkill for +/-/(). Optimized — one stack tracking running result and sign. On (, snapshot the current result and sign onto the stack and reset; on ), pop them and merge the inner result into the outer context. 
def calculate(s):
    stack = []
    result = num = 0
    sign = 1
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c in '+-':
            result += sign * num
            num = 0
            sign = 1 if c == '+' else -1
        elif c == '(':
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif c == ')':
            result += sign * num
            num = 0
            result *= stack.pop()           # saved sign
            result += stack.pop()           # saved outer result
    return result + sign * num
The push-two-things insight. Most candidates push only the result and forget the sign. Then 1 - (2 + 3) returns the wrong answer because the outer minus is lost. Push BOTH.

​
LC 71: Simplify Path (Medium)

Problem. Given a Unix-style absolute path, return the canonical form. Brute force. String manipulation with regex — error-prone and brittle for edge cases like /// or /... Optimized stack. Split by /. For each component: ignore . and empty strings; pop on ..; push otherwise. Join with /. 
def simplify_path(path):
    stack = []
    for part in path.split('/'):
        if part == '..':
            if stack: stack.pop()
        elif part and part != '.':
            stack.append(part)
    return '/' + '/'.join(stack)
Edge case test. /../ should return /. /home//foo/ should return /home/foo. /... should return /... (a literal directory named ...).

​
LC 739: Daily Temperatures (Medium) — Bridge to Monotonic Stack

Problem. For each day, return how many days until a warmer temperature. Brute force (O(n^2)). For each day, scan forward until warmer. Optimized monotonic stack (O(n)). Stack holds indices of days waiting for a warmer day. When today is warmer than the day on top, pop and record today - popped_index. 
def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []                              # indices of waiting days
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result                           # remaining indices keep result 0
Why O(n) despite the inner loop? Each index is pushed once and popped at most once — 2n operations max across the whole traversal. This is the amortized argument every interviewer asks about.

​
Common Mistakes

Caveats and Traps — The Bugs Every Stack Problem Hides:
  1. Popping an empty stack throws. Python IndexError, Java EmptyStackException/NoSuchElementException. Always guard with if stack: (Python), !stack.isEmpty() (Java), or !stk.empty() (C++) before every peek and pop.
  2. Expression evaluation: precedence is not free. Naive single-stack evaluation works for +/-/() but breaks on *// because of operator precedence. Use two stacks (operands + operators) or convert to RPN with the shunting-yard algorithm.
  3. String immutability in Java means you cannot just “pop a char” off a String. Use StringBuilder and call deleteCharAt(length-1), or maintain an actual Deque<Character>. Concatenating with s = s.substring(0, s.length()-1) is O(n) per pop, turning your O(n) algorithm into O(n^2).
  4. Wrong monotonic direction. Increasing stack finds next smaller; decreasing stack finds next greater. Get the direction backward and the algorithm computes the opposite of what you want — and the bug is invisible until you trace a small example.
  5. Storing values instead of indices. Without indices, you cannot compute distances (Daily Temperatures), widths (Largest Rectangle), or write results back to the correct position.
  6. Forgetting elements left on the stack at the end. In “next greater”, remaining elements have no answer (set to -1). In “largest rectangle”, remaining bars still have areas to compute. Use a sentinel value (append 0) to force a clean flush, or process the stack after the loop.
  7. Off-by-one in monotonic stack widths. The width on pop is i - stack[-1] - 1, NOT i - popped_index. Get this wrong and Largest Rectangle is silently incorrect.
Solutions and Idioms — Paired with the Caveats Above:
  1. Defensive guard: make if stack and ... your reflex on every while-loop condition. The Python and short-circuits, so the empty check costs nothing.
  2. For mixed precedence: use two stacks — one for numbers, one for operators — and pop-and-apply when you see an operator of equal or higher precedence than the new one. This is shunting-yard’s heart in three lines.
  3. Java string popping: use StringBuilder sb and sb.deleteCharAt(sb.length() - 1) — O(1) amortized. Or model the string as Deque<Character> directly.
  4. Monotonic direction mantra: say “I want next greater, so I keep a decreasing stack — when something larger arrives, it pops smaller waiters.” Reverse the words for “next smaller”. Speak it before you code.
  5. Default to indices: push i, not nums[i]. Recover the value via nums[stack[-1]] whenever you need it. Costs nothing, gains everything.
  6. Sentinel trick: append a dummy minimum value (heights.append(0) for histogram, temperatures.append(float('inf')) for daily temps) to force the final flush, eliminating the post-loop cleanup.
  7. Width incantation: “Width is current index minus new top minus one, because the new top is exclusive on the left and the current index is exclusive on the right.” Repeat until reflexive.

​
Curated LeetCode Practice List

The classic stack problem set, grouped by difficulty. Solve them in order within each tier.

​
Easy

#ProblemPattern Variant
20Valid ParenthesesBracket matching
232Implement Queue using StacksTwo-stack amortization
225Implement Stack using QueuesReverse trick
1047Remove All Adjacent DuplicatesPush-or-cancel
844Backspace String CompareStack simulation
682Baseball GameDirect stack ops

​
Medium

#ProblemPattern Variant
155Min StackAuxiliary stack for O(1) min
150Evaluate RPNOperand stack
71Simplify PathPath component stack
394Decode StringSave-restore context
739Daily TemperaturesMonotonic decreasing
503Next Greater Element IICircular monotonic
735Asteroid CollisionConditional pop on collision
901Online Stock SpanStreaming monotonic

​
Hard

#ProblemPattern Variant
84Largest Rectangle in HistogramMonotonic increasing
85Maximal RectanglePer-row histogram
224Basic CalculatorSave-restore context
772Basic Calculator IIITwo stacks plus precedence
42Trapping Rain WaterMonotonic decreasing

​
Common Mistakes

Avoid These Pitfalls:
  1. Empty stack access: Always check if stack is empty before peek/pop
  2. Forgetting to process remaining: Stack may still have elements after loop
  3. Wrong monotonic direction: Know when to use increasing vs decreasing stack
  4. Not storing indices: Often need index for distance calculations

​
Debugging Checklist

1

Check Empty Stack

Always verify !stack.empty() before peek() or pop()
2

Verify Matching Logic

For parentheses: opening pushes, closing pops and compares
3

Check Remaining Elements

After loop, stack may still have unprocessed elements
4

Validate Monotonic Direction

Increasing: pop smaller, Decreasing: pop larger
5

Track Indices vs Values

For distance calculations, store indices not values

​
Interview Problems by Company

ProblemCompanyKey Concept
Valid ParenthesesAll FAANGPush open, pop close
Baseball GameAmazonStack operations
Remove Outer ParensGoogleCounter or stack
Backspace StringGoogleStack simulation

​
Interview Tips

Script for interviews:
  1. “This is a matching problem, so I’ll use a stack.”
  2. “Opening brackets push, closing brackets pop and compare.”
  3. “If match fails or stack has leftovers, it’s invalid.”
  4. “For monotonic: I maintain a stack where elements are always sorted.”
Interviewer SaysYou Should Think
”Valid parentheses/brackets”Basic stack push/pop
”Next greater element”Monotonic decreasing stack
”Largest rectangle”Monotonic increasing stack
”Evaluate expression”Two stacks (operand + operator)
“Simplify path”Stack for directory navigation
def next_greater(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices
    
    for i in range(len(arr)):
        # Pop while current is greater than stack top
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    
    return result

​
Practice Problems

ProblemDifficultyLink
Valid ParenthesesEasyLeetCode 20
Min StackMediumLeetCode 155
Daily TemperaturesMediumLeetCode 739
Largest Rectangle in HistogramHardLeetCode 84
Basic CalculatorHardLeetCode 224

​
Practice Roadmap

1

Day 1: Basic Stack

  • Solve: Valid Parentheses, Min Stack
  • Focus: Push, pop, peek operations
2

Day 2: Expression Evaluation

  • Solve: Evaluate RPN, Decode String
  • Focus: Operand vs operator stacks
3

Day 3: Monotonic Stack

  • Solve: Next Greater Element, Daily Temperatures
  • Focus: When to pop from stack
4

Day 4: Hard Problems

  • Solve: Largest Rectangle, Basic Calculator
  • Focus: Complex monotonic patterns
Interview Tip: When you need to track “previous” or “next” elements with certain properties, think Monotonic Stack. When you see nested structures that must be resolved inside-out, think basic stack. Before coding any stack solution, ask yourself three things: (1) what goes on the stack (values or indices?), (2) when do I pop (what triggers resolution?), and (3) what do I do with remaining elements after the loop?

​
Interview Questions

Deep-dive questions that test real understanding of the Stack pattern, not just whether you can push and pop. Expect interviewers to keep digging past your first answer.
Difficulty: FoundationalWhat interviewers are really testing: Whether you understand why LIFO ordering is the correct invariant for matching nested structures, not just that “you use a stack for parentheses.” A candidate who can articulate the nesting argument can generalize to HTML tags, XML parsers, and compiler front-ends.Strong answer:
  • The key insight is that the most recently opened bracket must be the first one closed. That is exactly the LIFO property. If I see ({[, the [ must close before the {, which must close before the (. A stack naturally enforces this ordering.
  • Algorithm: Iterate through the string. Push every opening bracket. On a closing bracket, check that the stack is not empty AND the top matches. Pop on match, return false on mismatch. At the end, the stack must be empty — leftover openers mean unclosed brackets.
  • Why not a counter? A single counter works for one bracket type (just track open - close >= 0), but with multiple types it fails. ([)] has balanced counts but is invalid because the nesting order is wrong. Only a stack tracks the order of opens.
  • Real-world connection: This exact algorithm is the first pass of every compiler’s lexer and every JSON/XML parser. VS Code’s bracket matching uses this logic on every keystroke.
# The mapping trick: store closing -> opening for O(1) lookup
mapping = {`)`: `(`, `}`: `{`, `]`: `[`}
for char in s:
    if char in mapping:
        if not stack or stack[-1] != mapping[char]:
            return False
        stack.pop()
    else:
        stack.append(char)
return len(stack) == 0
Red flag answer: “I would use a counter for each bracket type and check they all end at zero.” This misses that ([)] is invalid despite balanced counts. Another red flag: not checking for empty stack before peeking — this is the #1 runtime error in stack problems.Follow-ups:
  1. What if the string contains non-bracket characters (like a * (b + c) - {d}}? How does your solution change? (Answer: simply skip characters not in the mapping or the opener set. The algorithm is identical otherwise.)
  2. What if I ask you to return the index of the first mismatched bracket instead of just true/false? How does your approach adapt? (Answer: track indices alongside characters on the stack. On mismatch, you have the index immediately. On leftover openers, the bottom of the stack gives the earliest unclosed index.)
Difficulty: IntermediateWhat interviewers are really testing: Whether you can identify the space-time trade-off at the heart of this design. O(1) min retrieval is only possible by trading space. This also tests whether you handle edge cases like duplicate minimums correctly — a subtle bug that trips up most candidates.Strong answer:
  • The core insight: a single stack cannot give O(1) minimum because removing an element might change the minimum, and you would need to scan. The fix is a second stack (the min stack) that mirrors the main stack’s minimum at every height.
  • Push: Push to main stack. Push to min stack if the value is <= the current min (or if min stack is empty). The <= is critical — not <. If I push [2, 0, 0] and use <, the min stack only has [2, 0]. When I pop the first 0, the min stack pops its 0, and now getMin() returns 2 even though a 0 is still on the main stack.
  • Pop: Pop from main stack. If the popped value equals the min stack’s top, pop the min stack too.
  • Alternative approach: Instead of a separate min stack, store (value, current_min) tuples on a single stack. Same O(n) space, slightly simpler logic, but doubles the memory per element.
  • Space analysis: Worst case (strictly decreasing input), the min stack is the same size as the main stack — O(n). Best case (strictly increasing input), the min stack has only one element. Average case depends on the distribution.
# The <= trap -- this MUST be <= not <
def push(self, val):
    self.stack.append(val)
    if not self.min_stack or val <= self.min_stack[-1]:
        self.min_stack.append(val)  # <= handles duplicates
Red flag answer: “Use a variable to track the minimum.” This breaks on pop — how do you know the new minimum? You would need to scan the entire stack, making pop O(n). Another red flag: using < instead of <= for the min stack push condition and not catching the duplicate minimum bug.Follow-ups:
  1. Can you implement MinStack using O(1) extra space (not O(n))? Hint: store something other than the raw value. (Answer: store the difference between the value and the current min. When the stored value is negative, it means we pushed a new minimum. On pop, use the difference to recover the previous min. This is clever but fragile with integer overflow.)
  2. What if I also need O(1) getMax()? Does one extra stack still suffice? (Answer: you need a third stack — a max stack. The pattern extends cleanly. Each auxiliary stack tracks one aggregate.)
Difficulty: IntermediateWhat interviewers are really testing: Whether you understand the amortized analysis behind monotonic stacks. Most candidates can code the solution but cannot explain why it is O(n) — they just say “we visit each element once.” The real proof requires reasoning about total push/pop operations across the entire traversal.Strong answer:
  • Naive approach: For each element, scan right until you find something greater. Worst case (sorted descending like [5, 4, 3, 2, 1]), every element scans to the end. That is O(n^2).
  • Monotonic stack approach: Maintain a stack where elements are in decreasing order (from bottom to top). For each new element, pop everything smaller — those popped elements just found their “next greater.” Then push the current element.
  • Why O(n): Each element is pushed exactly once and popped at most once. Total operations across the entire traversal: at most 2n. The while loop inside the for loop looks like it could be O(n) per iteration, but amortized across all iterations, the total pops cannot exceed n because we never pop something that was not previously pushed.
  • The way I think about it: The stack is like a waiting room. Elements sit in the waiting room until someone greater shows up. Once they are “resolved” (popped), they never come back. Since each element enters and exits the waiting room exactly once, total work is O(n).
  • Key detail: Store indices, not values. You almost always need the index for distance calculations (like in Daily Temperatures) or to write results back to an array.
# Each element enters the stack once, exits at most once = O(2n) = O(n)
for i in range(len(nums)):
    while stack and nums[i] > nums[stack[-1]]:
        idx = stack.pop()          # This element exits forever
        result[idx] = nums[i]       # Its "next greater" is nums[i]
    stack.append(i)                 # This element enters once
Red flag answer: “It is O(n) because we iterate through the array once.” This ignores the inner while loop. If a candidate cannot explain why the while loop does not make it O(n^2), they do not understand amortized analysis. Another red flag: confusing “monotonically increasing” and “monotonically decreasing” stacks — get the direction wrong and the algorithm finds next smaller instead of next greater.Follow-ups:
  1. When would you use a monotonic increasing stack versus a monotonic decreasing stack? Give a concrete problem for each. (Answer: decreasing stack for “next greater element” — you pop when you see something bigger. Increasing stack for “next smaller element” or “largest rectangle in histogram” — you pop when you see something smaller.)
  2. How would you adapt this for a circular array where the “next greater” can wrap around? (Answer: iterate through the array twice — conceptually 2n elements — using i % n for indexing. Only push during the first pass. The second pass resolves elements whose next greater wraps around.)
Difficulty: SeniorWhat interviewers are really testing: This is the hardest standard stack problem and a favorite at FAANG interviews. The interviewer wants to see if you can explain the width calculation on pop — specifically, why width = i - stack[-1] - 1 (not i - popped_index). Getting the width wrong is the most common bug, and understanding it requires grasping what the stack invariant guarantees about the elements between indices.Strong answer:
  • Why monotonic increasing: We want to find, for each bar, the largest rectangle using that bar as the shortest bar. A bar can extend left and right as long as all bars in that range are at least as tall. A monotonic increasing stack guarantees that when we pop a bar, everything between the new stack top and the current index is at least as tall as the popped bar.
  • The pop moment: When heights[i] < heights[stack[-1]], the bar at stack[-1] can no longer extend right (it hit something shorter). So we pop it and calculate its rectangle.
  • Width calculation — the tricky part: After popping index j, the width is NOT i - j. It is i - stack[-1] - 1 (or i if the stack is empty). Why? Because everything between the new stack top and i was already popped earlier, meaning those bars were all taller than heights[j]. So the rectangle of height heights[j] extends all the way from stack[-1] + 1 to i - 1.
  • Sentinel trick: Append a 0 to the end of the heights array. This forces all remaining elements to be popped, avoiding a separate cleanup loop after the main iteration. It is a clean simplification that interviewers appreciate.
  • Example: For [2, 1, 5, 6, 2, 3], when we hit the second 2 (index 4), we pop 6 (index 3): height = 6, width = 4 - 2 - 1 = 1, area = 6. Then pop 5 (index 2): height = 5, width = 4 - 1 - 1 = 2, area = 10. That width = 2 is the key — it includes index 3 because the 6 at index 3 was taller than 5.
# The sentinel avoids cleanup code after the loop
heights.append(0)
for i, h in enumerate(heights):
    while stack and heights[stack[-1]] > h:
        height = heights[stack.pop()]
        # Width extends from (new 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)
Red flag answer: Using width = i - popped_index instead of i - stack[-1] - 1. This is the single most common bug — it gives wrong answers when multiple bars have been popped. If a candidate cannot explain why previously-popped bars contribute to the width, they do not understand the invariant. Another red flag: not mentioning the sentinel trick and instead having a messy cleanup loop that handles edge cases differently.Follow-ups:
  1. How would you extend this to the Maximal Rectangle problem (LC 85), where you find the largest rectangle of 1s in a binary matrix? (Answer: treat each row as a histogram where the bar height is the number of consecutive 1s above. Run the largest rectangle algorithm on each row’s histogram. O(rows * cols) total.)
  2. What is the relationship between this problem and Trapping Rain Water? Can you use the same stack technique? (Answer: Trapping Rain Water uses a monotonic decreasing stack — you pop when you see something taller because it means a valley has been found. The height calculation uses the min of the two boundaries minus the popped bar’s height, and width is computed the same way. Same technique, opposite monotonicity.)
Difficulty: IntermediateWhat interviewers are really testing: Whether you can manage multiple types of state on the stack simultaneously. Parentheses matching only tracks one thing (the bracket type). Decode String requires tracking both a string accumulator and a repeat count, and correctly restoring state when you pop. This tests stack-as-state-machine thinking.Strong answer:
  • Why it is harder: In valid parentheses, the stack stores single characters. Here, we need to store context — the string we were building and the multiplier we saw before the [. When we hit ], we need to restore both.
  • The pattern: Maintain current_string and current_num as running accumulators. On [, push (current_string, current_num) onto the stack and reset both. On ], pop the saved state and compute prev_string + current_string * num. On digits, build the number. On letters, append to current_string.
  • Why two accumulators, not just one stack? You could use a single stack and push everything (digits, brackets, characters), but then the ] handler has to scan backwards through the stack to find the matching [ and extract the number. Using separate accumulators makes the ] handler O(1) instead of O(k) where k is the segment length.
  • Nested example walkthrough for 3[a2[bc]]:
    • Read 3 -> current_num = 3
    • Read [ -> push ("", 3), reset to current_str = "", current_num = 0
    • Read a -> current_str = "a"
    • Read 2 -> current_num = 2
    • Read [ -> push ("a", 2), reset to current_str = "", current_num = 0
    • Read b, c -> current_str = "bc"
    • Read ] -> pop ("a", 2), current_str = "a" + "bc" * 2 = "abcbc"
    • Read ] -> pop ("", 3), current_str = "" + "abcbc" * 3 = "abcbcabcbcabcbc"
# Stack stores (previous_string, repeat_count) tuples
for char in s:
    if char == '[':
        stack.append((current_str, current_num))
        current_str, current_num = "", 0
    elif char == ']':
        prev_str, num = stack.pop()
        current_str = prev_str + current_str * num
Red flag answer: Trying to use regex or recursion without being able to explain the stack-based iterative approach. The recursive solution works but interviewers specifically ask this to test iterative stack thinking. Another red flag: forgetting to handle multi-digit numbers (e.g., 12[a] — you need current_num = current_num * 10 + int(char), not just int(char)).Follow-ups:
  1. What if the encoding can have nested brackets without a number prefix, like [abc] meaning repeat once? How does your code handle this edge case? (Answer: initialize current_num to default 1 when pushing, or treat missing numbers as 1. The code needs a minor tweak — check if current_num == 0 on [ and default it.)
  2. What is the time complexity? It is not O(n) where n is the input length — explain why. (Answer: the output string can be exponentially larger than the input. For 10[10[10[a]]], the input is ~15 characters but the output is 1000 characters. Time is O(output_length), which can be much larger than input length. This matters for memory allocation decisions in production.)
Difficulty: SeniorWhat interviewers are really testing: Whether you understand how stacks can implement a state machine that evaluates expressions by saving and restoring evaluation context at each nesting level. The two-value push (result + sign) is the non-obvious insight that most candidates miss, and it reveals whether you can think about composing sub-expression results.Strong answer:
  • The challenge: Parentheses create nested evaluation contexts. The expression 1 - (2 + 3) requires evaluating 2 + 3 = 5 in its own context, then applying the - sign from the outer context. You need to “pause” the outer evaluation, compute the inner one, and “resume.”
  • Why push both result and sign: On (, push the running result so far and the sign before the parenthesis. Reset result to 0 and sign to 1. This creates a clean inner context. On ), finish the inner computation, then multiply by the saved sign and add to the saved result. This “merges” the inner result back into the outer context.
  • Walkthrough of 1 - (2 + 3):
    • Read 1 -> result = 1
    • Read - -> sign = -1
    • Read ( -> push (1, -1), reset result = 0, sign = 1
    • Read 2 -> result = 2
    • Read + -> sign = 1
    • Read 3 -> result = 5
    • Read ) -> pop (1, -1), result = 5 * (-1) + 1 = -4
  • Why not Shunting-yard or RPN conversion? Those work but are overkill for +, -, (, ). The direct evaluation with a stack is simpler and avoids building an intermediate representation. If the problem adds * and / with precedence, then Shunting-yard becomes worth the added complexity.
elif char == '(':
    stack.append(result)   # Save outer result
    stack.append(sign)     # Save sign before '('
    result = 0             # Fresh inner context
    sign = 1
elif char == ')':
    result += sign * number
    number = 0
    result *= stack.pop()  # Apply saved sign
    result += stack.pop()  # Add to saved result
Red flag answer: “Convert to Reverse Polish Notation first, then evaluate.” This is a valid approach but shows the candidate cannot reason about direct evaluation and may be falling back on the only technique they memorized. A worse red flag: not understanding why the sign is pushed — saying “we just push the result” and then getting wrong answers on expressions like 1 - (2 - 3).Follow-ups:
  1. How would you extend this to support * and / with correct operator precedence? (Answer: you now need two stacks — one for operands and one for operators — or you need to process * and / immediately while deferring + and - until later. Alternatively, convert to RPN with Shunting-yard then evaluate.)
  2. What happens with deeply nested expressions like ((((1 + 2)))) — is there a stack depth concern? (Answer: stack depth equals nesting depth. For user-generated input, you should add a max nesting depth check to prevent stack overflow in production. Compilers typically limit nesting depth for this reason.)
Difficulty: Intermediate (but reveals production-level thinking)What interviewers are really testing: Whether you have actually debugged stack code in practice or just written it once for a problem set. Candidates with real experience can rattle off specific failure modes and prevention strategies. This tests engineering maturity more than algorithmic knowledge.Strong answer:
  • Bug #1: Empty stack access. Calling peek() or pop() on an empty stack. This is the single most common runtime crash. Prevention: always guard with if stack (Python), !stack.isEmpty() (Java), or !stk.empty() (C++) before every access. Make it a reflex, not a conscious decision.
  • Bug #2: Forgetting remaining elements. After the main loop, the stack may still contain unprocessed elements. In “next greater element,” remaining elements have no greater element to their right and should be set to -1. In “largest rectangle,” remaining bars still need their areas calculated. Prevention: either process the stack after the loop or use a sentinel value (append 0 to the array) that forces everything to pop.
  • Bug #3: Storing values instead of indices. If you push values instead of indices, you lose positional information needed for distance calculations. Daily Temperatures returns how many days until warmer, not the temperature itself. Prevention: default to storing indices; you can always look up the value via arr[index].
  • Bug #4: Wrong monotonic direction. Using an increasing stack when you need decreasing (or vice versa). This flips the problem from “next greater” to “next smaller.” Prevention: before coding, explicitly write a comment like # monotonic decreasing: pop when current > top and verify against a small example.
  • Bug #5: Off-by-one in width calculations. In largest rectangle, the width is i - stack[-1] - 1, not i - popped_index. This is because previously-popped elements between the new top and i were taller. Prevention: trace through a small example (e.g., [2, 1, 5, 6, 2, 3]) on paper before coding.
# Defensive stack template
stack = []
for i in range(len(arr)):
    while stack and arr[i] > arr[stack[-1]]:  # Guard: 'stack' check
        idx = stack.pop()
        result[idx] = arr[i]
    stack.append(i)  # Always store indices

# Process remaining -- do not forget this
while stack:
    idx = stack.pop()
    result[idx] = -1  # No next greater element
Red flag answer: “I just test with examples and fix bugs as they come up.” This is not a strategy, it is hope. A strong candidate has a mental checklist they apply to every stack solution before running it. Another red flag: not knowing about the sentinel trick for avoiding the cleanup loop.Follow-ups:
  1. In Java, Stack<Integer> uses Integer objects. What subtle bug can occur when comparing stack top with a value using == instead of .equals()? (Answer: == compares object references, not values. For integers outside the cached range of -128 to 127, two Integer objects with the same value can have different references. stack.peek() == value may return false even when the values match. Always use .equals() or unbox explicitly.)
  2. How do you test a stack-based solution efficiently? What edge cases do you always check? (Answer: empty input, single element, all elements the same, strictly increasing input, strictly decreasing input, and the input that triggers the worst-case stack depth. These cover all boundary conditions for stack behavior.)
Difficulty: SeniorWhat interviewers are really testing: Whether you understand that the same problem can be solved with fundamentally different data structures, and whether you have the judgment to articulate when each approach is superior. The stack approach processes water in horizontal layers (bottom-up), while two pointers process it in vertical columns. Understanding both reveals deep algorithmic thinking.Strong answer:
  • How the stack approach works: Maintain a monotonic decreasing stack of indices. When height[i] > height[stack[-1]], a valley has been found. Pop the valley bottom, then calculate the water trapped between the new stack top (left boundary) and the current index (right boundary).
  • Water calculation on pop: height = min(height[stack[-1]], height[i]) - height[popped] (bounded height minus valley floor). width = i - stack[-1] - 1. Water for this layer = height * width. This adds water in horizontal layers, not vertical columns.
  • Key difference from two-pointer: Two pointers calculate water column by column (vertical slices): for each position, water += min(left_max, right_max) - height[i]. The stack calculates water layer by layer (horizontal slices): for each valley, compute the rectangular strip of water trapped.
  • When to prefer the stack:
    • When the input is a stream and you do not have the full array upfront. The stack processes left-to-right and does not need a right-to-left pass.
    • When the problem variation asks “how many distinct pools of water are formed” — the stack naturally segments water into contiguous pools as each valley is processed.
  • When to prefer two pointers: When you need O(1) space (the stack is O(n) worst case) and you have the full array.
stack = []
water = 0
for i in range(len(height)):
    while stack and height[i] > height[stack[-1]]:
        bottom = stack.pop()
        if not stack:  # No left boundary
            break
        h = min(height[stack[-1]], height[i]) - height[bottom]
        w = i - stack[-1] - 1
        water += h * w
    stack.append(i)
Red flag answer: “I would just use two pointers, the stack approach is unnecessary.” This shows inflexibility and suggests the candidate only knows one approach. Even worse: confusing the monotonic direction — using an increasing stack instead of decreasing, which would find valleys incorrectly.Follow-ups:
  1. What is the worst-case space complexity of the stack approach? Give a concrete input that triggers it. (Answer: O(n) when the input is strictly decreasing like [5, 4, 3, 2, 1]. Nothing gets popped until you hit a taller bar, so all indices accumulate on the stack.)
  2. If the input heights can be floating-point numbers, does the stack approach still work correctly? Are there precision concerns? (Answer: the algorithm works identically. However, floating-point addition is not associative, so the order in which horizontal layers are summed can cause tiny precision differences compared to the two-pointer approach. For financial or engineering calculations, you might need to use decimal types or track an error bound.)
Difficulty: Foundational (but the system design nuance elevates it)What interviewers are really testing: Whether you can bridge algorithmic knowledge to a real system design. This also tests whether you think about invalidation — the forward stack must be cleared on new navigation, which is a state management concern that trips up candidates who only think about push/pop.Strong answer:
  • Two stacks: A back_stack and a forward_stack. The current page is a separate variable (not on either stack).
  • Navigate to new URL: Push current page onto back_stack. Set current = new URL. Clear the forward stack entirely. This is the critical insight — visiting a new page invalidates all forward history. This is the same behavior you see in every browser.
  • Back button: Push current page onto forward_stack. Pop back_stack and set it as current.
  • Forward button: Push current page onto back_stack. Pop forward_stack and set it as current.
  • Edge cases: Back with empty back_stack -> disable the button (no-op). Same for forward. This maps to how browsers grey out the buttons.
  • Real-world considerations: In production, you would not store full page objects on the stack — you would store URLs or session history entry IDs. Browsers also cap history depth (Chrome limits to ~50 entries per tab) to prevent memory bloat. You would also handle pushState/replaceState from the History API, which adds entries without actual navigation.
class BrowserHistory:
    def __init__(self, homepage):
        self.current = homepage
        self.back_stack = []
        self.forward_stack = []

    def visit(self, url):
        self.back_stack.append(self.current)
        self.current = url
        self.forward_stack.clear()  # Invalidate forward history

    def back(self):
        if not self.back_stack:
            return self.current  # No-op
        self.forward_stack.append(self.current)
        self.current = self.back_stack.pop()
        return self.current
Red flag answer: “Use one stack and an index pointer.” While this works (and is actually how LeetCode 1472 models it), it does not demonstrate understanding of why two stacks are the natural model for back/forward navigation. Another red flag: forgetting to clear the forward stack on new navigation — this would allow users to go “forward” to a page that is no longer part of the navigation path.Follow-ups:
  1. If the user clicks back 5 times rapidly, should you render all 5 intermediate pages or skip to the final destination? How does this affect your design? (Answer: in a real browser, each back is rendered, but rapid clicks debounce and the intermediate renders may be interrupted. Your stack logic stays the same — the rendering layer handles the optimization.)
  2. How would you add a steps parameter to back and forward (like LC 1472) so the user can go back N pages at once? What is the time complexity? (Answer: pop min(N, stack size) elements in a loop, pushing each to the other stack. O(N) per call. You could optimize to O(1) with an array + pointer instead of two stacks, which is why the LC solution often uses that model.)
Difficulty: SeniorWhat interviewers are really testing: Whether you can extend a known pattern to handle a structural constraint (circularity). The “iterate twice” trick is not obvious, and explaining why it is correct requires understanding that one full extra pass is sufficient to resolve all wrap-around dependencies. This also tests modular arithmetic fluency.Strong answer:
  • The problem with circularity: In a linear array, elements at the end have no “next greater” to the right. In a circular array, the search wraps around — the next greater element for the last element could be the first element.
  • The trick: Iterate 2n times using i % n for indexing. The first pass (i = 0 to n-1) works exactly like the linear version. The second pass (i = n to 2n-1) revisits elements, allowing wrap-around resolution. Only push indices during the first pass (i < n), or push i % n throughout — but only write results for indices less than n.
  • Why one extra pass suffices: After the first pass, the stack contains indices whose next greater element was not found in the linear scan. During the second pass, each of these elements gets compared against elements from the start of the array. Since the second pass covers the entire array, every element gets a chance to be the “next greater” for every unresolved element. No element needs more than one full wrap-around to find its answer (or confirm none exists).
  • What about elements that truly have no next greater? In a circular array, an element has no next greater only if it is the maximum of the entire array. After 2n iterations, such elements remain on the stack. Their result stays as the initialized -1.
def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []

    for i in range(2 * n):
        while stack and nums[i % n] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i % n]
        if i < n:
            stack.append(i)  # Only push real indices
    return result
Red flag answer: “Just duplicate the array and run the normal algorithm.” While conceptually similar, actually concatenating the array wastes O(n) space and creates confusion about which indices are “real.” Using i % n achieves the same effect with O(1) extra space. Another red flag: iterating 3n or more times “just to be safe” — this shows the candidate does not understand why 2n is exactly sufficient.Follow-ups:
  1. What is the time and space complexity? Is the 2n iteration still O(n)? (Answer: yes, O(n) time — each of the n elements is pushed once and popped at most once. The second pass only causes pops, no new pushes. Space is O(n) for the stack and result array.)
  2. What if instead of “next greater,” I ask for the “next greater element that is at least K positions away” in a circular array? Does the monotonic stack still work directly? (Answer: not directly. The monotonic stack resolves the nearest next greater. For a minimum-distance constraint, you would need to delay processing — only pop an element when the current index is at least K positions ahead of it. This requires careful index arithmetic with the modular wrapping.)

​
Interview Q&A Rapid-Fire (Rich Format)

The four problems below mirror the format you will see in our other DSA chapters: strong answer framework, real LeetCode example with full code, three senior follow-ups, common wrong answers, and further reading.
Strong Answer Framework:
  1. Identify the constraint. “All four operations — push, pop, top, getMin — must be O(1). A naive single stack makes getMin O(n).”
  2. Introduce the auxiliary structure. “I will keep a parallel min-stack tracking the running minimum at every height of the main stack.”
  3. Push rule. Push to main always. Push to min-stack only if the new value is <= the current min (the <= is critical for duplicates).
  4. Pop rule. Pop main always. If the popped value equals the min-stack top, pop min-stack too.
  5. Justify <= vs <. Trace [2, 0, 0]: with <, popping the first 0 removes it from the min-stack and getMin returns 2 while a 0 is still on main. With <=, the second 0 is also pushed onto min-stack, preserving correctness.
Real LeetCode Example — LC 155: Min Stack
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:    # <= for duplicates
            self.min_stack.append(val)

    def pop(self) -> None:
        top = self.stack.pop()
        if top == self.min_stack[-1]:
            self.min_stack.pop()

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

    def getMin(self) -> int:
        return self.min_stack[-1]
Time O(1) for every operation. Space O(n) worst case (strictly decreasing input).
Senior Follow-up 1: “Can you achieve O(1) extra space (not O(n))?” — Yes, by storing differences. Push val - current_min onto a single stack. When the stored value is negative, it signals a new min (and you can recover the previous min by subtraction). Clever but fragile — integer overflow with extreme values is a real concern.
Senior Follow-up 2: “What if I also need O(1) getMax?” — Add a third stack (max-stack) following the same pattern, push when val >= max_stack[-1]. Each auxiliary stack tracks one aggregate. The pattern composes cleanly.
Senior Follow-up 3: “What is the worst-case extra memory?” — O(n) when the input is strictly decreasing. Every push to main also pushes to min-stack. Best case is strictly increasing input, where min-stack only holds the very first element.
Common Wrong Answers:
  • “Track the minimum in a single variable” — breaks on pop. After popping the current min, you do not know the new min without scanning.
  • “Use < instead of <= for the min-stack push condition” — silently wrong on duplicate minimums.
  • “Scan the stack on getMin” — O(n) per call, fails the constraint.
Further Reading:
Strong Answer Framework:
  1. Recognize the postfix advantage. “RPN is unambiguous — no parentheses, no precedence rules. The stack evaluates it in one linear pass.”
  2. State the algorithm. Iterate tokens. If number, push. If operator, pop two operands, apply, push result.
  3. Order matters for non-commutative operators. For a - b, the second pop is a (the left operand) and the first pop is b (the right operand). Same for division.
  4. Handle integer division semantics. Some problems require truncation toward zero (LC 150 specifically), not Python’s floor division.
  5. Verify the final state. After processing all tokens, exactly one value remains on the stack: the result.
Real LeetCode Example — LC 150: Evaluate Reverse Polish Notation
def evalRPN(tokens):
    stack = []
    for tok in tokens:
        if tok in {'+', '-', '*', '/'}:
            b = stack.pop()              # right operand popped first
            a = stack.pop()              # left operand popped second
            if tok == '+': stack.append(a + b)
            elif tok == '-': stack.append(a - b)
            elif tok == '*': stack.append(a * b)
            else:                         # division: truncate toward zero
                stack.append(int(a / b))   # NOT a // b
        else:
            stack.append(int(tok))
    return stack[0]
Time O(n), space O(n).
Senior Follow-up 1: “Why int(a / b) instead of a // b in Python?” — Python’s // is floor division, which rounds toward negative infinity. The problem requires truncation toward zero. int(a / b) truncates correctly: int(-7 / 2) == -3 (truncated), while -7 // 2 == -4 (floored). This is a common subtle bug.
Senior Follow-up 2: “How would you handle infix expressions instead of postfix?” — Convert with the shunting-yard algorithm: use two stacks (one for operators, one for output). Pop higher-or-equal precedence operators when pushing a new operator. Or evaluate directly with two stacks (operands and operators) and the same precedence logic.
Senior Follow-up 3: “What if the expression has function calls like max(a, b) or unary operators like -x?” — Extend the parser: function names go on the operator stack with their argument count. Unary minus is detected by context (no preceding operand). The shunting-yard algorithm handles all this; LeetCode rarely tests it but production calculators must.
Common Wrong Answers:
  • “Pop in the wrong order” — a - b becomes b - a. The interviewer is watching for whether you say “left operand popped second” out loud.
  • “Use // for division” — wrong for negative numbers (LC 150 specifically tests this).
  • “Build a parse tree first” — correct but overkill; the stack handles RPN in one pass with no tree.
Further Reading:
Strong Answer Framework:
  1. Articulate the LIFO insight. “The most recently opened bracket must be the first one closed — exactly the LIFO property of a stack.”
  2. Reject the counter approach. A single counter passes ([)] (balanced counts but invalid nesting). Only a stack tracks order.
  3. Set up a closer-to-opener map for O(1) match lookup.
  4. One pass through the string. Push openers; on closers, the stack top must be the matching opener.
  5. End-state check. Empty stack means valid — leftover openers mean unclosed brackets.
Real LeetCode Example — LC 20: Valid Parentheses
def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
        else:                              # c is a closer
            if not stack or stack.pop() != pairs[c]:
                return False
        # NB: empty-stack guard is required to avoid IndexError on stray closers
    return not stack
Time O(n), space O(n).
Senior Follow-up 1: “Now make this incremental — support addChar(c) and isValid() queries.” — Same stack, but expose it as state. addChar does the push or pop; isValid checks if the stack is empty AND no mismatch has occurred. Keep a is_dirty flag for early failures.
Senior Follow-up 2: “What if the input contains non-bracket characters like ‘a + (b * c)’?” — Skip characters not in the opener set or closer map. Algorithm is otherwise unchanged.
Senior Follow-up 3: “Return the index of the first mismatch instead of true/false.” — Track indices alongside characters on the stack. On mismatch, the current index is the answer. On leftover openers at the end, the bottom of the stack gives the earliest unclosed index.
Common Wrong Answers:
  • “Use one counter per bracket type” — passes ([)], which is wrong.
  • “Use regex to repeatedly remove (), [], {}” — works for matched-only but is O(n^2) in the worst case.
  • “Forget the empty-stack check” — crashes on inputs that start with a closer like ).
Further Reading:
Strong Answer Framework:
  1. Recognize the pattern. “This is ‘next greater element’ but instead of recording the value, I record the day distance.”
  2. Brute force first. O(n^2) — for each day, scan forward. Too slow.
  3. Monotonic stack of indices. Days waiting for warmer weather sit on the stack; today’s temperature pops every day on top that is colder.
  4. Why indices, not values. We need i - j to compute the wait distance.
  5. Default to 0. Days remaining on the stack at the end never found a warmer day — the array’s default zero already handles them.
  6. Prove O(n) amortized. Each day is pushed once and popped at most once.
Real LeetCode Example — LC 739: Daily Temperatures
def daily_temperatures(temps):
    n = len(temps)
    result = [0] * n
    stack = []                            # indices of waiting days
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j             # day distance, not temperature value
        stack.append(i)
    return result
Time O(n), space O(n).
Senior Follow-up 1: “Solve in O(1) extra space (not counting the output array).” — Traverse right-to-left. For each day, walk forward using the already-computed answers as jump pointers (similar to skip-list traversal). Implementation is trickier but achieves the constant-space goal.
Senior Follow-up 2: “Now I want days until a STRICTLY COLDER day.” — Flip the comparison: monotonic increasing stack, pop when temps[i] < temps[stack[-1]]. The skeleton is identical; only the comparison flips.
Senior Follow-up 3: “Apply this in a streaming setting — temperatures arrive one per day.” — This becomes LC 901 (Online Stock Span). Maintain a stack of (value, span_count) pairs. On a new value, accumulate spans of all popped smaller values into the current span. Amortized O(1) per call.
Common Wrong Answers:
  • “Brute force scanning forward from each day” — O(n^2), times out.
  • “Push values, not indices” — cannot compute the distance i - j.
  • “Forget that remaining stack elements should map to 0” — relying on default initialization is fine but candidates often add a redundant cleanup loop and break it.
Further Reading: