Day 17: Stacks

DAY 17 / 30 · WEEK 3

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

Scanning "{[()()]}" with a stack of open brackets.

Press Play or Step to begin.

Step 0 / ...

▶ Play⏭ Step↺ Reset🔀 Shuffle

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

A min stack: each frame stores both its value and the running minimum at that level.

Press Play or Step to begin.

Step 0 / ...

▶ Play⏭ Step↺ Reset🔀 Shuffle

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("{[()()]}")

Index	Char	Action	Stack (bottom → top)
0	{	opener — push	{
1	[	opener — push	{ [
2	(	opener — push	{ [ (
3	)	top is ( — matches → pop	{ [
4	(	opener — push	{ [ (
5	)	top is ( — matches → pop	{ [
6	]	top is [ — matches → pop	{
7	}	top is { — matches → pop	(empty)
—	—	end of string, stack is empty	return true

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

Approach	Time	Space	Why
Valid Parentheses	O(n)	O(n)	Each character is pushed or popped at most once (a single pass). Worst case — all openers, e.g. "(((((" — every character sits on the stack at once.
Min Stack (push, pop, top, getMin)	O(1) each	O(n)	Every operation only touches the top of one or two arrays — no loop, no scan. The space cost is a second array the same size as the first, to store each level’s running min.

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

1. Valid Parentheses

Given a string containing just ()[]{}", determine if the input string is valid — today’s core example, worked through above.

Hint: Think about which data structure naturally “undoes” the most recent thing first. Then make sure you handle both edge cases: a closer arriving with nothing on the stack, and openers still left on the stack after the string ends.

Solution:

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;
}

2. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.

Hint: O(1) getMin rules out scanning the whole stack on every call. What if a second, parallel stack tracked the running minimum at each level, updated at push time?

Solution:

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];
  }
}

3. Daily Temperatures

Given daily temperatures, return an array where answer[i] is the number of days until a warmer temperature (0 if there isn’t one).

Hint: This isn’t about matching brackets — it’s about finding the next warmer day. Keep a stack of indices whose temperatures are still “waiting” for something warmer (a monotonically decreasing stack); when a new temperature beats the top of the stack, that’s the answer for it.

Solution:

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

1. What ordering principle describes a stack?

• LIFO — Last In, First Out
• FIFO — First In, First Out
• No fixed order — any element can be removed

Show answer

A stack is Last In, First Out — the most recently pushed value is always the first one popped.

2. In Valid Parentheses, what must you check before popping the stack when a closing bracket arrives?

• That the stack isn’t empty
• That the stack is sorted
• That the string has at least 3 characters left

Show answer

Popping or peeking an empty stack has nothing to compare against — in JS it silently returns undefined instead of throwing, so skipping this check produces a wrong answer instead of a crash.

3. Why must you check the stack is empty again AFTER the scan finishes, not just during it?

• Unclosed openers (e.g. “(()”) never fail mid-scan, only a final emptiness check catches them
• It’s purely a performance optimization
• It isn’t necessary — the loop already guarantees correctness

Show answer

A string like “(()” never triggers a mismatch mid-scan, but leaves an unclosed opener on the stack — only checking for emptiness after the loop ends catches that.

4. What are the time and space complexity of Valid Parentheses?

• O(n) time, O(n) space
• O(n) time, O(1) space
• O(n²) time, O(n) space

Show answer

Every character is pushed or popped at most once (O(n) time); the stack can hold up to n characters in the worst case, e.g. an all-openers string (O(n) space).

5. How does Min Stack achieve O(1) getMin()?

• A parallel stack tracks the running minimum at each level as values are pushed
• It keeps the whole stack sorted at all times
• It rescans the entire stack each time getMin() is called

Show answer

A second, parallel stack stores the running minimum at each level, updated on every push and popped alongside the value stack — the top of that min stack is always the O(1) answer, no scanning needed.