DAY 17 / 30 · WEEK 3

Stacks

Goal of the day

• Understand LIFO (last in, first out) and the three core operations — push (add to top), pop (remove from top), peek (look at the top without removing it) — all O(1).
• Use a stack to solve Valid Parentheses: match opening and closing brackets by always comparing the incoming bracket against whatever is currently on top.
• See how a stack can also track its own running minimum (Min Stack) in O(1), by storing extra bookkeeping alongside each pushed value instead of rescanning on every query.

Concept

A stack is a collection where you can only add or remove from one end — the top. Think of a stack of plates: you place a new plate on top (push), and when you need one, you take the top plate off (pop) — you never pull a plate from the middle or bottom without first removing everything above it. This ordering is called LIFO: Last In, First Out. It's the opposite of a queue (FIFO — First In, First Out), which we'll build on Day 18.

A stack supports exactly three operations, all O(1):

• push(value) — add value to the top.
• pop() — remove and return the top value.
• peek() — return the top value without removing it. (LeetCode's Min Stack API below calls this same operation top() — same thing, different name.)

In JavaScript, a plain array already behaves like a stack if you only ever use .push() and .pop() — both operate on the end of the array, which we simply treat as "the top." No special class is required.

Stacks show up whenever a problem needs to undo or match against "whatever happened most recently" — undo history in an editor, the back button in a browser, and, today's core example, matching brackets: when a closing bracket arrives, it must match the most recently opened, still-unclosed bracket — exactly what a stack's top gives you for free.

Diagram: push and pop always happen at the top

Diagram: Min Stack — track the running minimum alongside each value

Interactive visualization: Valid Parentheses, character by character

Interactive visualization: Min Stack — push/pop with running min

The code: Valid Parentheses

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' }; // closer -> the opener it must match

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);                 // opener — push it, we'll need it later
    } else {
      // closer — first make sure there's something to match against
      if (stack.length === 0 || stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0; // true only if every opener got matched and popped
}

Line by line:

• pairs maps each closing bracket to the opening bracket it must match — looking it up is O(1), so the whole scan stays O(n).
• Every opening bracket is simply pushed — nothing to check yet, since we don't know what will need to match it until a closer shows up.
• For a closing bracket, stack.length === 0 || stack.pop() !== pairs[ch] does two jobs in one line thanks to short-circuiting: first it guards against popping an empty stack (an unmatched closer with nothing open), and only if that passes does it actually pop and compare the result against what this closer requires.
• The final return stack.length === 0 is easy to forget — a string like "((()" never hits the return false inside the loop (every individual comparison "succeeds" because no closer ever mismatches), but it leaves unmatched openers sitting on the stack. Only checking emptiness at the very end catches that.

Dry run: isValid("{[()()]}")

Every closer matched the top of the stack at the moment it arrived, and the stack was back to empty by the end — that combination is exactly what "valid" means.

Complexity

Interview corner

• Why is a stack (not a queue) the natural fit for matching brackets? The rule is "the most recently opened bracket must be the first one closed" — that's exactly LIFO order. A queue would try to match brackets in the order they were opened (FIFO), which is backwards for nesting.
• What's the very first thing you check when a closing bracket arrives? Whether the stack is empty.
  ⚠ Trap: forgetting to guard pop()/peek() with a length check is the most common way this problem breaks — popping an empty array returns undefined in JS instead of throwing, so a missing guard doesn't crash, it just silently produces a wrong answer that's easy to miss in testing.
• Why isn't "the stack became empty at some point" enough to call the string valid? You must also check it's empty at the very end, after the whole string is scanned — a string like "(()" never triggers a mismatch mid-scan, but it leaves an unclosed '(' sitting on the stack forever.
  ↳ Common follow-up: "What if the string also has other characters mixed in, like letters or digits?" — skip anything that isn't one of the six bracket characters (else if (isCloser(ch)) { ... } else continue;); the interviewer is checking whether you generalize the stack idea instead of assuming the input is only brackets.
• How does Min Stack get O(1) getMin() without rescanning? A second, parallel stack records the running minimum as of that push — each push(val) also pushes Math.min(val, currentMin) onto the min stack, and each pop() pops both together. The top of the min stack is always the answer.
• What's the space trade-off of that approach? O(n) extra space (a second array the same size as the first) buys O(1) time on every single operation, instead of O(1) extra space but an O(n) rescan every time getMin() is called. For a structure whose whole point is fast repeated queries, that trade is almost always worth it.

How to talk through it out loud: name the invariant before writing code — "I'll use a stack because the most recently opened bracket has to close first, that's LIFO." Then narrate each branch as you type it: "opener → push it. Closer → first check the stack isn't empty, then check the top matches. At the very end, it's only valid if the stack is also empty." Interviewers are listening for you to say the empty-stack guard and the final-emptiness check out loud, not just for code that happens to pass the example they gave you.

Practice problems

function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.length === 0 || stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

class MinStack {
  constructor() {
    this.stack = [];     // actual values
    this.minStack = [];  // running min at each level
  }
  push(val) {
    this.stack.push(val);
    const currentMin = this.minStack.length === 0
      ? val
      : Math.min(val, this.minStack[this.minStack.length - 1]);
    this.minStack.push(currentMin);
  }
  pop() {
    this.stack.pop();
    this.minStack.pop();
  }
  top() {
    return this.stack[this.stack.length - 1];
  }
  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  const stack = []; // indices, temperatures decreasing bottom to top

  for (let i = 0; i < n; i++) {
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop();
      answer[idx] = i - idx;
    }
    stack.push(i);
  }
  return answer;
}

Quiz