Frontend Beauty
ESC

Type to search the knowledge base.

Min Stack

Stack with O(1) push, pop, top, and getMin — pair each value with the min so far, or dual stacks.

intermediate3 min read
  • dsa
  • stack
  • interview
  • Google
  • Meta

The problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // -3
minStack.pop();
minStack.top();    // 0
minStack.getMin(); // -2

Brute force

On getMin, scan the stack. O(n) min — rejected by the problem statement.

Optimal: store min alongside each value

Each entry is { val, min } where min is the minimum of the stack including this val.

class MinStack {
  private stack: { val: number; min: number }[] = [];

  push(val: number): void {
    const min = this.stack.length
      ? Math.min(val, this.stack[this.stack.length - 1].min)
      : val;
    this.stack.push({ val, min });
  }

  pop(): void {
    this.stack.pop();
  }

  top(): number {
    return this.stack[this.stack.length - 1].val;
  }

  getMin(): number {
    return this.stack[this.stack.length - 1].min;
  }
}

Dual-stack variant

Main stack of values + min stack that pushes when val <= currentMin (use <= so duplicates of the min pop correctly).

class MinStackDual {
  private vals: number[] = [];
  private mins: number[] = [];

  push(val: number): void {
    this.vals.push(val);
    if (!this.mins.length || val <= this.mins[this.mins.length - 1]) {
      this.mins.push(val);
    }
  }

  pop(): void {
    const v = this.vals.pop();
    if (v === this.mins[this.mins.length - 1]) this.mins.pop();
  }

  top(): number {
    return this.vals[this.vals.length - 1];
  }

  getMin(): number {
    return this.mins[this.mins.length - 1];
  }
}
Time O(1) all ops
Space O(n)

Edge cases

  • Single element
  • Many equal mins: push -1,-1; pop one; min still -1 — need <= on dual stack
  • Decreasing then increasing sequences
  • Constraints usually guarantee ops on non-empty stack

Common bugs

  • Dual stack only pushes on strict < → duplicate mins break on pop
  • Computing min only at push time without storing history
  • Off-by-one on empty after pop

Interview delivery

  1. O(1) min means precompute on push.
  2. Pair method or dual stack.
  3. Stress-test equal minimums.
  4. State O(1)/O(n).

Trace dual-stack

push -2 → vals[-2], mins[-2]
push 0 → vals[-2,0], mins[-2] (0 > min)
push -3 → vals[-2,0,-3], mins[-2,-3]
getMin → -3
pop → pop -3, also pop min
getMin → -2

Why <= not < on dual stack

push -1, push -1. If you only push min on strict <, mins has one -1. First pop removes a -1 but mins still shows -1 (ok accidentally)… until you pop again: vals empty of -1 but mins still has -1 → wrong. Use <= so each equal min is stacked.

Pair encoding alternative

Some solutions push 2*val - min encodings to save space — clever, error-prone in interviews. Prefer explicit pairs or dual stacks.

API contract

Clarify whether pop returns the value (LC void) and whether empty ops are possible. Don’t crash on empty if constraints guarantee safety — still write defensive optional checks if time allows.

Further reading