Stack Pattern Explained

What is the Stack Pattern?

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates: you can only add or remove plates from the top. The last plate you put on the stack is the first one you can take off.

Stacks are fundamental in computer science and appear everywhere: function call stacks, undo operations in text editors, browser back buttons, and countless interview problems. Understanding when and how to use a stack can turn an O(n²) brute force solution into an elegant O(n) algorithm.

When to Use a Stack

Consider using a stack when:

• Matching brackets or parentheses - The most classic stack problem. Each opening bracket waits for its closing match
• Expression evaluation - Converting infix to postfix, evaluating postfix expressions, or parsing mathematical notation
• Monotonic problems - Finding the next greater/smaller element, daily temperatures, or stock span
• Backtracking state - DFS traversal, undo operations, or maintaining history of choices
• Reversing sequences - Reversing strings, words, or linked lists
• Nested structure processing - Parsing HTML/XML, nested function calls, or recursive-like iteration

Pattern Variations

1. Basic Stack Operations

The fundamental stack operations are push (add to top), pop (remove from top), and peek (view top without removing). In TypeScript, arrays work perfectly as stacks.

// Using an array as a stack in TypeScript
const stack: number[] = []

// Push - O(1)
stack.push(1)  // stack: [1]
stack.push(2)  // stack: [1, 2]
stack.push(3)  // stack: [1, 2, 3]

// Peek - O(1)
const top = stack[stack.length - 1]  // top: 3

// Pop - O(1)
const removed = stack.pop()  // removed: 3, stack: [1, 2]

// Check if empty
const isEmpty = stack.length === 0  // false

// Key insight: All operations are O(1) - this is what makes
// stacks so powerful for solving problems efficiently

2. Matching Brackets Pattern

The most common stack pattern. For every opening bracket, we push it onto the stack. For every closing bracket, we check if it matches the most recent opening bracket.

function isValid(s: string): boolean {
  const stack: string[] = []
  const pairs: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{'
  }

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      // Opening bracket - push to stack
      stack.push(char)
    } else {
      // Closing bracket - check for match
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false
      }
    }
  }

  // Valid only if all brackets matched
  return stack.length === 0
}

// Example: isValid("([{}])") → true
// Stack evolution: [(] → [([)] → [([])] → [([{}] → [([] → [( → [] → true

// Example: isValid("([)]") → false
// Stack: [(] → [([)] → pop ']' expects '[' but got '(' → false

3. Monotonic Stack (Increasing)

A monotonic increasing stack maintains elements in ascending order from bottom to top. When we encounter a larger element, we pop smaller elements and process them. This pattern is perfect for “next greater element” problems.

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length
  const result = new Array(n).fill(0)
  const stack: number[] = []  // Stack stores indices, not values

  for (let i = 0; i < n; i++) {
    // Pop all days with lower temperature
    while (stack.length > 0 &&
           temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const prevDay = stack.pop()!
      result[prevDay] = i - prevDay  // Days until warmer
    }
    stack.push(i)
  }

  return result
}

// Example: dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])
// Output: [1, 1, 4, 2, 1, 1, 0, 0]
//
// Day 0 (73°): Wait 1 day for 74°
// Day 2 (75°): Wait 4 days for 76°
// Day 6 (76°): No warmer day, stays 0

// Key insight: Each element is pushed and popped at most once
// Total operations = 2n = O(n) time complexity

4. Monotonic Stack (Decreasing)

A monotonic decreasing stack maintains elements in descending order. Useful for “next smaller element” or finding the span of consecutive smaller elements.

function nextSmallerElement(nums: number[]): number[] {
  const n = nums.length
  const result = new Array(n).fill(-1)
  const stack: number[] = []  // Decreasing stack (stores indices)

  for (let i = 0; i < n; i++) {
    // Pop all elements greater than current
    while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
      const idx = stack.pop()!
      result[idx] = nums[i]
    }
    stack.push(i)
  }

  return result
}

// Example: nextSmallerElement([4, 8, 5, 2, 25])
// Output: [2, 5, 2, -1, -1]
//
// 4 → next smaller is 2
// 8 → next smaller is 5
// 5 → next smaller is 2
// 2, 25 → no smaller element to the right

5. Min Stack

A stack that supports push, pop, and getMin operations all in O(1) time. The trick is to store the minimum value at each state of the stack.

class MinStack {
  private stack: number[] = []
  private minStack: number[] = []

  push(val: number): void {
    this.stack.push(val)

    // Track minimum at each level
    if (this.minStack.length === 0) {
      this.minStack.push(val)
    } else {
      this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]))
    }
  }

  pop(): void {
    this.stack.pop()
    this.minStack.pop()
  }

  top(): number {
    return this.stack[this.stack.length - 1]
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1]
  }
}

// Example usage:
// const minStack = new MinStack()
// minStack.push(-2)  // stack: [-2], minStack: [-2]
// minStack.push(0)   // stack: [-2, 0], minStack: [-2, -2]
// minStack.push(-3)  // stack: [-2, 0, -3], minStack: [-2, -2, -3]
// minStack.getMin()  // returns -3
// minStack.pop()     // stack: [-2, 0], minStack: [-2, -2]
// minStack.getMin()  // returns -2

Common Problems & Solutions

Problem 1: Evaluate Reverse Polish Notation

Question: Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /. Each operand may be an integer or another expression.

function evalRPN(tokens: string[]): number {
  const stack: number[] = []
  const operators = new Set(['+', '-', '*', '/'])

  for (const token of tokens) {
    if (operators.has(token)) {
      // Pop two operands (order matters for - and /)
      const b = stack.pop()!
      const a = stack.pop()!

      let result: number
      switch (token) {
        case '+': result = a + b; break
        case '-': result = a - b; break
        case '*': result = a * b; break
        case '/': result = Math.trunc(a / b); break  // Truncate toward zero
        default: result = 0
      }

      stack.push(result)
    } else {
      // Push operand
      stack.push(parseInt(token))
    }
  }

  return stack[0]
}

// Example: evalRPN(["2", "1", "+", "3", "*"])
// Step by step:
// "2" → stack: [2]
// "1" → stack: [2, 1]
// "+" → pop 1, 2; push 2+1=3 → stack: [3]
// "3" → stack: [3, 3]
// "*" → pop 3, 3; push 3*3=9 → stack: [9]
// Result: 9 (equivalent to (2 + 1) * 3)

Problem 2: Largest Rectangle in Histogram

Question: Given an array of integers representing the heights of bars in a histogram, find the area of the largest rectangle that can be formed within the histogram.

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = []  // Stack of indices
  let maxArea = 0

  // Add sentinel value to handle remaining elements
  const h = [...heights, 0]

  for (let i = 0; i < h.length; i++) {
    // Pop bars taller than current
    while (stack.length > 0 && h[i] < h[stack[stack.length - 1]]) {
      const height = h[stack.pop()!]

      // Width extends from previous stack element to current index
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1

      maxArea = Math.max(maxArea, height * width)
    }
    stack.push(i)
  }

  return maxArea
}

// Example: largestRectangleArea([2, 1, 5, 6, 2, 3])
// Output: 10 (rectangle with height 5, width 2 using bars at index 2 and 3)
//
// This is a classic monotonic stack problem - we find the largest
// rectangle by determining how far each bar can extend left and right

Time & Space Complexity

Time Complexity: O(n) for most stack problems. Each element is pushed and popped at most once, giving us 2n operations total.
Space Complexity: O(n) in the worst case when all elements are pushed onto the stack. For problems like valid parentheses with balanced input, average case is O(n/2).

The key insight for monotonic stacks: while there's a nested loop, each element enters and exits the stack exactly once. This amortized analysis gives us linear time despite the apparent O(n²) structure.

Pro Tips

• Store indices, not values: In monotonic stack problems, storing indices gives you both the value (via the original array) and positional information for distance calculations
• Use sentinel values: Adding a 0 at the end of the array in histogram problems forces all remaining elements to be processed
• Draw the stack state: Trace through examples by drawing the stack after each operation. This reveals the pattern
• Watch the pop order: In expression evaluation, the first popped element is the second operand (order matters for subtraction and division)
• Empty stack checks: Always check if the stack is empty before popping or peeking to avoid runtime errors
• Consider both directions: Some problems require processing the array twice (left-to-right and right-to-left) or using two stacks

Practice Problems

Ready to test your understanding? Try these LeetCode problems:

• Easy: Valid Parentheses (#20), Implement Queue using Stacks (#232), Baseball Game (#682)
• Medium: Daily Temperatures (#739), Min Stack (#155), Evaluate Reverse Polish Notation (#150), Decode String (#394)
• Hard: Largest Rectangle in Histogram (#84), Trapping Rain Water (#42), Basic Calculator (#224)

Continue Learning

• Two Pointers Pattern — Another O(n) technique for array problems
• Sliding Window Technique — Complementary pattern for subarray problems
• Binary Search Guide — Essential divide-and-conquer technique
• Start Practicing — Apply stack patterns to real interview problems