Stack Pattern

Why this pattern matters for LeetCode

Bracket matching fails with a simple counter the moment you have multiple bracket types. A closing bracket must match the most recently opened bracket — and a counter can't tell you what that was. A stack gives you exactly that: instant access to the last unresolved item. Push openers, pop and compare on closers. If the stack is empty at the end, everything matched.

What the Stack pattern is

A stack processes elements in LIFO (last-in, first-out) order — the last thing pushed is the first thing popped. It excels at matching problems, nested structure, and 'undo' semantics. The core intuition: when an element's validity depends on the most recently seen element, a stack gives you instant access to that element. Push when you encounter something unresolved; pop and check when you encounter its matching closer.

Reach for Stack when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Stack

• ✓Validating bracket/parenthesis strings (Valid Parentheses)
• ✓Tracking the minimum or maximum element dynamically as you push/pop (Min Stack)
• ✓Finding the next greater element in an array (monotonic stack)
• ✓Evaluating expressions in postfix or prefix notation
• ✓Implementing undo functionality

When NOT to use Stack

• ✕You need to process elements in first-in, first-out order — use a Queue instead
• ✕You need random access by index — use an array directly
• ✕The matching doesn't depend on the most recent element — a counter may be sufficient
• ✕You need to traverse in level order — use a Queue for BFS

Better alternative: In those cases, a Queue (for FIFO/BFS) or a simple counter (for single bracket types) may be simpler.

JavaScript code template

Valid Parentheses core pattern — O(n) time, O(n) space

function isValid(s) {
  const stack = [];
  const pairs = {
    ")": "(",
    "}": "{",
    "]": "[",
  };

  for (const char of s) {
    if (!pairs[char]) {
      // It's an opening bracket — push it
      stack.push(char);
    } else {
      // It's a closing bracket — must match the top of the stack
      if (stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  // If anything is left, some openers were never closed
  return stack.length === 0;
}

Build a map from each closing bracket to its expected opening bracket. For each character: if it's an opener, push it. If it's a closer, pop from the stack and compare to the expected opener. If they don't match, or the stack was empty (nothing to pop), return false. At the end, check that the stack is empty — any remaining openers were never closed.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Create an empty stack and a map from closing brackets to their matching opening brackets.
2. 2Loop through each character in the input.
3. 3If the character is an opener (not in the map), push it onto the stack.
4. 4If the character is a closer (in the map), pop from the stack and compare to the expected opener.
5. 5If the stack was empty when you tried to pop, or the popped value doesn't match — return false.
6. 6After the loop, return true only if the stack is empty (all openers were matched).

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Valid Parentheses

  Push openers, pop closers, check they match — the textbook stack problem.

  Free→
• Min Stack

  Track the minimum using an auxiliary stack that mirrors the main stack's minimums.

  Premium→
• Daily Temperatures

  Monotonic stack — push indexes, pop when a warmer day is found.

  Premium→
• Evaluate Reverse Polish Notation

  Push operands, pop two when you hit an operator, push the result back.

  Premium→
• Largest Rectangle in Histogram

  Monotonic increasing stack to track the left boundary of each bar.

  Premium→
• Baseball Game

  Push scores, pop on 'D' and 'C' operations — classic LIFO stack simulation.

  Premium→

Common mistakes beginners make

• ✕Popping from an empty stack without checking — always guard with stack.length > 0 before popping, or handle the undefined case.
• ✕Forgetting to check that the stack is empty at the end — unmatched opening brackets won't trigger an early return.
• ✕Using a counter instead of a stack — a counter works for one bracket type but breaks the moment you mix '(', '[', and '{'.
• ✕Not building the closing-to-opening lookup table — manually chaining if/else for each bracket type gets messy and error-prone.

Stack vs Queue

Choose the right tool for the job.

Time and space complexity

You visit each character exactly once. Each character is pushed to the stack at most once and popped at most once — O(1) per character. In the worst case (all opening brackets, no closers), you push every character, giving O(n) space for the stack.

Frequently asked questions

Why can't I just use a counter for bracket matching?

A counter works if you only have one type of bracket. But with '(', '[', and '{', a counter can't tell you what the most recent unmatched opener was. ')' might need to match '(' or might be invalid after '['. Only a stack preserves the order and type of openers.

What does LIFO mean and why does it matter for brackets?

LIFO means Last In, First Out — the most recently added item is the first to come out. For brackets, this is exactly what you need: each closing bracket must match the most recently opened unclosed bracket. The stack naturally gives you that most-recent item instantly.

When should I use a Stack vs a Queue?

Stack (LIFO) when you need to process things in reverse arrival order — bracket matching, DFS, backtracking, undo. Queue (FIFO) when you need to process things in arrival order — BFS, level-order traversal, task scheduling.

Is Valid Parentheses really O(n)?

Yes. You visit each character once. Each push and pop is O(1). The total number of pushes and pops is at most n (each character is pushed at most once, popped at most once). So the full loop is O(n) time and the stack uses at most O(n) space.