Stack

MNEMONIC Pop everything you tower over.

PATTERN LIFO bookkeeping — deferring and pairing

A stack stores work that is incomplete until some future condition is met. You push something now and pop it later when you encounter its match or resolution. Classic examples:

• Bracket matching. Push each opening bracket; when a closing bracket arrives, pop and verify the pair.
• Expression evaluation (RPN / postfix). Push operands; on an operator, pop two operands, compute, push the result.
• Undo / most-recent-first.Any "reverse chronological" access pattern maps directly onto a stack.

In all these cases the stack is essentially a scratchpad of open obligations waiting to be closed.

KEY IDEA The monotonic stack — O(n) next-greater / next-smaller

A monotonic stack maintains elements in sorted order by aggressively popping elements that violate the invariant as each new element arrives. Every element is pushed exactly once and popped at most once, so the total work is O(n) even though there is a nested while loop inside a for.

Crucially, you almost always push the index, not the value — that way, when you pop, you can compute distances or widths.

COST Amortized O(n) — why the nested loop is not O(n²)

The inner while loop can pop at most n elements across the entire outer loop — the total number of pops is bounded by the total number of pushes, which is exactly n. This is the standard amortized argument.

SHAPES Decreasing vs increasing stack — how to choose

• Monotonic decreasing (values ↓ from bottom to top). Pop when the incoming value is greater. Answers "next greater element" or "next warmer day" — popped element's answer is the current index/value.
• Monotonic increasing (values ↑ from bottom to top). Pop when the incoming value is smaller. Answers "next smaller element", "previous smaller", and histogram-style span queries.

For histogram / span problems (Largest Rectangle, Car Fleet) you often need both boundaries — loop left-to-right with an increasing stack and use the index gap to compute width.

RUN IT Pop everything you tower over

TRIGGERS When you see ___ → reach for ___

Reach for a stack when you need to remember things in reverse order— either to match/cancel them (brackets, pairs) or to resolve a "what was the last X before this?" query (monotonic). If the problem involves the nearest element that is greater or smaller, the monotonic stack is almost always the right tool.

RED FLAGSWhen it's NOT this pattern

• You need FIFO order (process oldest first).That's a queue, not a stack. A common mistake is using a stack when BFS level-order traversal is required.
• You need random access by index. Stacks only expose the top. If you need to read or update an arbitrary position, you want a plain array or a different data structure.
• You need the global minimum or maximum efficiently.A heap (priority queue) serves that role. A plain stack can only tell you what's on top, not the extreme of all current elements — unless you augment it (see Min Stack, #155).
• The "next greater" is in a 2-D grid or graph. The monotonic stack is linear; 2-D extensions usually require BFS/DFS or a different sweep technique.

TEMPLATE Basic match / pair stack

When → Any problem that involves matching opening and closing delimiters or pairing elements that cancel each other out (brackets, tags, asterisks). Push openings, pop and verify on each closing.

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

  for (const ch of s) {
    if (!close[ch]) {
      stack.push(ch);               // opening bracket → defer it
    } else {
      if (stack.pop() !== close[ch]) return false;  // must match top
    }
  }
  return stack.length === 0;        // nothing left unmatched
}

TEMPLATE Monotonic decreasing — next greater

When → The problem asks for the next element to the right that is greater (or the distance to it). Keep a decreasing stack of indices; pop when the incoming value exceeds the top.

// Monotonic DECREASING stack → find the NEXT GREATER element to the right.
// Stack holds indices of elements waiting for their "answer".
function nextGreater(arr: number[]): number[] {
  const n = arr.length;
  const res = new Array<number>(n).fill(-1);
  const stack: number[] = [];         // indices, values are decreasing top→bottom

  for (let i = 0; i < n; i++) {
    // Pop while the current element is GREATER than the top of stack.
    // Those popped elements have found their next-greater answer.
    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
      res[stack.pop()!] = arr[i];
    }
    stack.push(i);                    // push index, NOT value
  }
  return res;                         // remaining indices keep -1 (no greater)
}

TEMPLATE Monotonic increasing — next smaller

When → The problem asks for the next element to the right that is smaller, or for a left-boundary (previous smaller) by iterating right-to-left. Keep an increasing stack of indices; pop when the incoming value is less than the top.

// Monotonic INCREASING stack → find the NEXT SMALLER element to the right.
// Stack holds indices of elements waiting for their "answer".
function nextSmaller(arr: number[]): number[] {
  const n = arr.length;
  const res = new Array<number>(n).fill(-1);
  const stack: number[] = [];         // indices, values are increasing top→bottom

  for (let i = 0; i < n; i++) {
    // Pop while the current element is SMALLER than the top of stack.
    while (stack.length && arr[i] < arr[stack[stack.length - 1]]) {
      res[stack.pop()!] = arr[i];
    }
    stack.push(i);
  }
  return res;
}

TEMPLATE Histogram / span — increasing stack of indices

When → Problems that compute a max area or span bounded by a shorter bar on either side (Largest Rectangle in Histogram, Trapping Rain Water variant). Append a sentinel 0 to flush the stack cleanly at the end.

// Largest rectangle in histogram — monotonic increasing stack of bar indices.
// When a shorter bar arrives, pop taller bars and compute their max-width rectangle.
function largestRectangle(heights: number[]): number {
  const bars = [...heights, 0];       // sentinel 0 flushes all remaining bars
  const stack: number[] = [];         // increasing stack of indices
  let maxArea = 0;

  for (let i = 0; i < bars.length; i++) {
    while (stack.length && bars[i] < bars[stack[stack.length - 1]]) {
      const h = bars[stack.pop()!];
      // Width: from the new top-of-stack (exclusive) to i (exclusive)
      const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, h * w);
    }
    stack.push(i);
  }
  return maxArea;
}

PITFALL Popping an empty stack

In JavaScript/TypeScript, Array.prototype.pop() on an empty array returns undefined instead of throwing. This silently corrupts comparisons. Always guard with stack.length > 0 before popping, or assert with stack.pop()! only after the guard.

PITFALL Pushing value instead of index

Monotonic stack problems almost always require the index on the stack, not the value. When you pop to record an answer, you need the index to compute the distance (i − j) or the span width. Storing the value makes that calculation impossible. Retrieve the value via arr[stack.top] during comparison.

PITFALL Strict vs non-strict comparison — handling duplicates

Whether you use > or >= (and < vs <=) in the "pop while" condition decides what happens with equal elements. Using >=pops duplicates eagerly (only the rightmost duplicate records the "next greater"); using >keeps duplicates on the stack so each one can answer independently. Read the problem statement carefully — "strictly greater" vs "greater or equal" changes the invariant.

PITFALL Forgetting to process the leftover stack after the loop

After the main loop finishes, elements still on a monotonic stack have no next greater/smaller element — their answer is -1 (or 0, depending on the problem). For match/pair problems, a non-empty stack after the loop means unmatched opening brackets — the string is invalid. A common bug is returning early without this check.

PROBLEMS