Stack Patterns — Matching, Undo & Monotonic Stacks

A stack shines whenever the most recent unfinished thing must be handled first. Three interview shapes:

Shape 1: Matching pairs

// Valid parentheses — push openers, pop and match on closers
function isValid(s) {
  const pair = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (!pair[ch]) stack.push(ch);                 // opener
    else if (stack.pop() !== pair[ch]) return false;
  }
  return stack.length === 0;
}

Solve it now: Valid Parentheses — the hidden tests include the sneaky "([" case.

Shape 2: Process-with-undo

Path simplification (cd .. pops a directory), backspace string compare, collapsing adjacent duplicates — anything where a new item can cancel the previous one.

Shape 3: Monotonic stack (the medium-level differentiator)

"For each element, find the next greater element" — brute force O(n²), monotonic stack O(n). Keep a stack of indexes whose answer is unknown, in decreasing value order:

function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = [];                        // indexes, values decreasing
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      res[stack.pop()] = nums[i];          // nums[i] answers them!
    }
    stack.push(i);
  }
  return res;
}
// [2,1,5,3] → [5,5,-1,-1]

Each index is pushed and popped at most once → O(n). This one template solves: daily temperatures ("days until warmer"), stock spans, largest rectangle in histogram, and trapping rain water variants.

Spot it when…

• Brackets/matching/nesting → shape 1.
• "Previous item might get cancelled" → shape 2.
• "Next/previous greater/smaller element for each position" → monotonic stack.

Related practice: Trapping Rain Water (two-pointer AND stack solutions exist — knowing both is interview gold).