Stack Fundamentals & Design Patterns - Complete Interview Guide

Overview

The Stack is one of the most fundamental data structures in computer science and a favorite topic in coding interviews. Its LIFO (Last In, First Out) property makes it perfect for problems involving:

• Matching pairs (parentheses, tags)
• Expression evaluation (postfix, infix)
• Backtracking (undo operations, DFS)
• Design problems (Min Stack, browser history)

Why Interviewers Love Stack Problems

1. Tests fundamental understanding - Basic push/pop operations seem simple, but using them correctly requires solid logic
2. Elegant solutions - Many complex problems become simple with stack thinking
3. Design patterns - Stack-based designs test your ability to create efficient data structures
4. Foundation for harder topics - Monotonic stack, recursion elimination, parsing

---

Stack Basics

LIFO Principle

Stack Operations:
                    ┌───┐
    push(3) ───────►│ 3 │ ← top
                    ├───┤
                    │ 2 │
                    ├───┤
                    │ 1 │
                    └───┘
    
    pop() returns 3:
                    ┌───┐
                    │ 2 │ ← new top
                    ├───┤
                    │ 1 │
                    └───┘

Core Operations

Operation	Description	Time Complexity
push(x)	Add element to top	O(1)
pop()	Remove and return top element	O(1)
peek()/top()	Return top element without removing	O(1)
isEmpty()	Check if stack is empty	O(1)

When to Use a Stack

• Processing elements in reverse order
• Matching opening/closing symbols
• Tracking state that needs to be undone
• Converting recursion to iteration

---

Problem 1: Valid Parentheses (LC 20)

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

A string is valid if:

1. Open brackets must be closed by the same type of brackets
2. Open brackets must be closed in the correct order
3. Every close bracket has a corresponding open bracket of the same type

Intuition

Think of brackets like nesting dolls:

• Each opening bracket starts a new “level”
• Each closing bracket should match the most recent unmatched opening bracket
• A stack naturally tracks this “most recent” relationship

Input: "({[]})"

Step by step:
  '(' → push → stack: ['(']
  '{' → push → stack: ['(', '{']
  '[' → push → stack: ['(', '{', '[']
  ']' → matches '[' → pop → stack: ['(', '{']
  '}' → matches '{' → pop → stack: ['(']
  ')' → matches '(' → pop → stack: []
  
Result: stack empty → VALID ✓

Solution

JavaPythonJavaScript

Loading...

Interactive Visualization

Initializing...

Complexity Analysis

• Time: $O(n)$ - single pass through the string
• Space: $O(n)$ - worst case all opening brackets

Edge Cases

• Empty string → valid
• Single bracket → invalid
• All opening brackets → invalid
• Mismatched types "(]" → invalid
• Wrong order "([)]" → invalid

---

Problem 2: Evaluate Reverse Polish Notation (LC 150)

Problem Statement

Evaluate the value of an arithmetic expression in Reverse Polish Notation (postfix notation).

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note: Division truncates toward zero.

What is RPN?

Reverse Polish Notation places operators after their operands:

Infix	RPN
1 + 2	1 2 +
(1 + 2) * 3	1 2 + 3 *
4 + 13 / 5	4 13 5 / +

Intuition

RPN is designed for stack-based evaluation:

1. Number → push onto stack
2. Operator → pop two operands, calculate, push result

Input: ["2", "1", "+", "3", "*"]

Step by step:
  "2" → push 2 → stack: [2]
  "1" → push 1 → stack: [2, 1]
  "+" → pop 1, pop 2 → 2+1=3 → push 3 → stack: [3]
  "3" → push 3 → stack: [3, 3]
  "*" → pop 3, pop 3 → 3*3=9 → push 9 → stack: [9]
  
Result: 9

Solution

JavaPythonJavaScript

Loading...

Interactive Visualization

Initializing...

Key Points

• Order matters for - and /: When you pop b then a, compute a op b
• Division truncates toward zero: In Java/JS, this is automatic for integers; Python needs int(a/b)
• Always exactly one element left: The final result

Complexity Analysis

• Time: $O(n)$ - process each token once
• Space: $O(n)$ - stack can hold up to n/2 numbers

---

Problem 3: Min Stack (LC 155)

Problem Statement

Design a stack that supports:

• push(val) - Push element onto stack
• pop() - Remove top element
• top() - Get top element
• getMin() - Retrieve minimum element in O(1) time

The Challenge

The naive approach to getMin() is O(n) - scan the entire stack. But we need O(1)!

Why can’t we just sort the data? Because a stack is a dynamic structure:

• Elements are constantly added and removed
• Sorting would cost O(n log n) per query
• We need the minimum to update automatically as elements come and go

The Key Insight: Prefix Minimum

Here’s the brilliant insight that makes O(1) possible: Min Stack is essentially maintaining a prefix minimum!

Think about it - at any point, the elements in the stack are exactly [element_0, element_1, ..., element_top]. The minimum is simply:

min(element_0, element_1, ..., element_top) = prefixMin[top]

Why does this work for a stack?

1. LIFO property: Elements can only be removed from the top
2. When we push element at index i: prefixMin[i] = min(prefixMin[i-1], element[i])
3. When we pop: The prefix minimum at position top-1 is still valid!

Example: Push sequence [3, 5, 2, 7, 1]

Index:     0    1    2    3    4
Element:   3    5    2    7    1
PrefixMin: 3    3    2    2    1   ← min of all elements up to this point

When we pop 1: prefixMin[3] = 2 is still correct for elements [3,5,2,7]
When we pop 7: prefixMin[2] = 2 is still correct for elements [3,5,2]

Why don’t we need to re-scan when popping?

The magic is that prefix minimums are independent of future elements. The minimum of [3,5,2] doesn’t change whether or not we later push 7, 1, or anything else. This is fundamentally different from problems like “sliding window minimum” where the window can shift.

Intuition: Two Stack Approach

Maintain a second stack that tracks the minimum at each level:

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

Main Stack    Min Stack     Explanation
   []            []         Initial state
   [-2]          [-2]       -2 is current min
   [-2,0]        [-2]       0 > -2, min unchanged
   [-2,0,-3]     [-2,-3]    -3 <= -2, push to min stack
   
getMin() → -3 (top of min stack)

   [-2,0]        [-2]       Pop -3, equals min, pop from min stack too
   
top() → 0
getMin() → -2

Solution

JavaPythonJavaScript

Loading...

Interactive Visualization

Initializing...

Why Does This Work?

• When we push a value, if it’s a new minimum (or equal), we record it
• When we pop, if we’re removing the current minimum, we pop from min stack too
• The top of min stack is always the minimum of the current stack state

Alternative: Single Stack with Pairs

Store (value, currentMin) pairs:

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

Complexity Analysis

• Time: $O(1)$ for all operations
• Space: $O(n)$ - min stack can be same size as main stack

---

Extended: Min Queue

Now that we understand Min Stack, a natural question arises: Can we build a Min Queue?

A queue is FIFO (First In, First Out), which seems fundamentally different from stack’s LIFO. In a queue, we remove from the front but add at the back - so the “prefix minimum” trick doesn’t directly apply.

The Challenge with Queues

Queue: [3, 1, 4, 1, 5] (front to back)
       ↑              ↑
    dequeue here   enqueue here

When we dequeue 3: the min is still 1 ✓
When we dequeue 1: the min changes to 1 (the other one)

The minimum depends on elements in the middle - we can’t just track prefixes!

Solution: Two Min-Stacks

Remember how we built a Queue using two stacks? We can do the same with two Min Stacks!

inStack:  receives pushes, tracks min for "right half"
outStack: serves pops, tracks min for "left half"

Overall min = min(inStack.getMin(), outStack.getMin())

Each stack independently maintains its prefix minimum. When we transfer elements from inStack to outStack, they get reversed - which is exactly what we need for FIFO behavior, and we rebuild the prefix minimum for outStack during the transfer.

JavaPythonJavaScript

Loading...

Why Two Min-Stacks Work

1. Push: Add to inStack with updated minSoFar → O(1)
2. Pop: Pop from outStack, transfer if empty → Amortized O(1)
3. GetMin: Compare tops of both stacks → O(1)

Each element is transferred at most once, so amortized O(1) for all operations.

Use Cases

• Sliding window minimum (when window size varies)
• Queue-based algorithms needing min/max tracking
• Rate limiting with min/max metrics

---

Extended: Two-Way Min Deque

What if we need a double-ended queue (deque) that supports O(1) minimum queries?

A deque allows push/pop from both ends:

• pushFront(val), pushBack(val)
• popFront(), popBack()
• getMin() - still O(1)!

The Problem with Prefix Minimum

With a deque, elements can be removed from either end. Our prefix minimum trick breaks down:

Deque: [3, 1, 4]  prefixMin from left: [3, 1, 1]
                  suffixMin from right: [1, 1, 4]

If we popFront() removing 3: need suffix info
If we popBack() removing 4: need prefix info

Neither prefix nor suffix alone is sufficient!

Solution: Monotonic Deque

Instead of tracking prefix minimums, we maintain a monotonic deque - a deque where elements are always in non-decreasing order.

Main deque:      [3, 1, 4, 1, 5]
Monotonic deque: [1, 1, 5]  ← only elements that could be the minimum

Key insight: If we push 2, then 3, then 1...
- When 1 arrives, 3 and 2 can NEVER be the minimum while 1 exists
- So we remove them from the monotonic deque!

The front of the monotonic deque is always the current minimum.

JavaPythonJavaScript

Loading...

How Monotonic Deque Maintains Minimum

On pushBack(val):

1. Remove all elements > val from back (they’ll never be min)
2. Add val to back

On pushFront(val):

1. Remove all elements > val from front
2. Add val to front

On popFront/popBack:

1. If the removed value equals the front/back of monotonic deque, remove it too

GetMin: Simply return front of monotonic deque!

Comparison: Min Stack vs Min Queue vs Min Deque

Feature	Min Stack	Min Queue	Min Deque
Core Technique	Prefix minimum	Two min-stacks	Monotonic deque
Push	O(1)	O(1)	O(1) amortized
Pop	O(1)	Amortized O(1)	O(1)
GetMin	O(1)	O(1)	O(1)
Space	O(n)	O(n)	O(n)
Complexity	Simple	Medium	Most complex

Real-World Applications

1. Sliding Window Maximum/Minimum (LC 239) - Classic monotonic deque problem
2. Jump Game VI (LC 1696) - DP with monotonic deque optimization
3. Shortest Subarray with Sum at Least K (LC 862) - Monotonic deque for optimization

---

Problem 4: Implement Stack using Queues (LC 225)

Problem Statement

Implement a LIFO stack using only queue operations: push, peek/front, pop, empty.

Intuition

A queue is FIFO, but we need LIFO. The trick: rotate elements after each push so the newest element is at the front.

Push 1: queue = [1]
Push 2: queue = [2] → rotate → queue = [2, 1]
Push 3: queue = [3, 2, 1] → but after rotation: 
        [3] → [3,2,1] → rotate 2 times → [3,2,1]
        
Actually: push 3, then move 2 elements to back:
        [2,1,3] → [1,3,2] → [3,2,1]

Solution

JavaPythonJavaScript

Loading...

How the Rotation Works

Before push(3): queue = [2, 1]  (2 at front = stack top)

1. Add 3 to back:    queue = [2, 1, 3]
2. Move 2 to back:   queue = [1, 3, 2]
3. Move 1 to back:   queue = [3, 2, 1]

Now 3 is at front = new stack top ✓

Complexity Analysis

• Push: $O(n)$ - need to rotate n-1 elements
• Pop/Top/Empty: $O(1)$

---

Problem 5: Implement Queue using Stacks (LC 232)

Problem Statement

Implement a FIFO queue using only stack operations: push, pop, peek, empty.

Intuition: Two Stack Approach

Use two stacks:

• inStack: receives all pushes
• outStack: serves all pops/peeks

When outStack is empty, transfer all elements from inStack - this reverses the order, giving us FIFO!

push(1), push(2), push(3):
  inStack = [1, 2, 3]  (3 at top)
  outStack = []

pop():
  outStack empty → transfer: pop from inStack, push to outStack
  inStack = []
  outStack = [3, 2, 1]  (1 at top)
  
  pop from outStack → returns 1 ✓ (first in, first out!)

Solution

JavaPythonJavaScript

Loading...

Why Amortized O(1)?

Each element is:

1. Pushed once to inStack - O(1)
2. Moved once to outStack - O(1)
3. Popped once from outStack - O(1)

Total: 3 operations per element, amortized O(1).

Complexity Analysis

• Push: $O(1)$
• Pop/Peek: Amortized $O(1)$, worst case $O(n)$
• Empty: $O(1)$

---

Templates & Patterns

Pattern 1: Matching/Pairing

Use when you need to match opening and closing elements:

def matchingPattern(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in pairs.values():  # Opening
            stack.append(char)
        elif char in pairs:          # Closing
            if not stack or stack.pop() != pairs[char]:
                return False
    
    return len(stack) == 0

Pattern 2: Expression Evaluation

Use for postfix/prefix evaluation or calculator problems:

def evaluateExpression(tokens):
    stack = []
    
    for token in tokens:
        if is_operator(token):
            b, a = stack.pop(), stack.pop()
            stack.append(apply_operator(a, b, token))
        else:
            stack.append(parse_number(token))
    
    return stack[0]

Pattern 3: Design with Auxiliary Stack

Use when you need O(1) access to some aggregate (min, max, etc.):

class DesignStack:
    def __init__(self):
        self.stack = []
        self.aux_stack = []  # Tracks min/max/etc.
    
    def push(self, val):
        self.stack.append(val)
        if should_update_aux(val, self.aux_stack):
            self.aux_stack.append(val)
    
    def pop(self):
        val = self.stack.pop()
        if self.aux_stack and val == self.aux_stack[-1]:
            self.aux_stack.pop()
        return val

---

Complexity Analysis

Problem	Time	Space
Valid Parentheses	O(n)	O(n)
Evaluate RPN	O(n)	O(n)
Min Stack (all ops)	O(1)	O(n)
Stack using Queues	O(n) push, O(1) others	O(n)
Queue using Stacks	Amortized O(1)	O(n)

---

Interview Tips

Common Mistakes to Avoid

1. Forgetting to check empty stack before pop() or peek()
2. Wrong operand order in RPN: when you pop b then a, compute a op b
3. Not handling edge cases: empty input, single element
4. Integer division truncation: Python’s // rounds toward negative infinity; use int(a/b) for truncation toward zero

How to Explain Your Approach

1. State the problem clearly: “I need to match brackets in LIFO order”
2. Explain why stack: “Stack’s LIFO property naturally handles…”
3. Walk through an example: Use a small input to demonstrate
4. Discuss edge cases: Empty input, all same type, mismatched

Follow-up Questions Interviewers May Ask

• Min Stack: “What if we need max instead of min?” → Same approach
• Valid Parentheses: “What if there are other characters?” → Skip non-bracket chars
• RPN: “How would you handle parentheses (infix notation)?” → Shunting-yard algorithm
• Stack/Queue conversions: “Can you do it with one queue/stack?” → Yes, with different tradeoffs

---

Summary

Key takeaways for stack problems:

1. LIFO is powerful - perfect for matching, backtracking, and reversing order
2. Auxiliary stacks enable O(1) operations that seem impossible
3. Two-stack trick can convert between LIFO and FIFO
4. Always check for empty before accessing top element

Master these fundamentals, and you’ll be well-prepared for stack questions in any interview!