DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Stacks & Monotonic Stack

A stack is Last-In-First-Out ordering, and it comes up constantly for tracking "what's the most recent unresolved thing" — matching brackets, undo history, and anywhere a recursive call's implicit stack could be swapped out for an explicit one.

When a stack beats recursion

Recursion tracks its own call state implicitly, on the language's call stack. An explicit stack — just an array you push and pop — gives you the identical LIFO ordering without consuming actual stack frames, which matters once recursion depth risks hitting a language's call-stack limit (a few thousand to tens of thousands of frames, depending on the runtime), or when you need to pause and inspect the in-progress state mid-traversal in a way a call stack doesn't expose.

function isBalanced(s) {
  const stack = [];
  const closerToOpener = { ')': '(', ']': '[', '}': '{' };

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else if (ch in closerToOpener) {
      if (stack.pop() !== closerToOpener[ch]) return false;   // mismatched, or nothing to pop
    }
  }
  return stack.length === 0;    // every opener must have found its closer
}

Monotonic stack — the next-greater-element shape

A monotonic stack maintains an invariant — its values stay increasing, or stay decreasing, from bottom to top — and pops off whatever violates that invariant as new elements arrive. The moment an element gets popped, that's precisely the moment it has found its answer.

function nextGreaterElement(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];       // stores INDICES; values at those indices stay decreasing, bottom to top

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop();
      result[idx] = nums[i];      // nums[i] is exactly the next greater element for idx
    }
    stack.push(i);
  }
  return result;
}

This looks like a nested loop — a for with a while inside it — but every index is pushed exactly once and popped at most once across the entire run, so the total combined work of every iteration of that inner while is O(n), not O(n²). It's the same amortized argument as the variable-size sliding window above: bound the total number of pushes and pops across the whole algorithm, not the worst case of a single iteration.

The problem shape this solves: "next greater/smaller element," "daily temperatures until it gets warmer," "stock span" — anywhere the question is, for every element, the nearest element to one side that satisfies some comparison. A plain nested loop answers this in O(n²); the monotonic stack answers it in O(n) by never re-scanning an element once it's found its answer or been proven irrelevant.

Practice this on Code Lab: Stacks