4.8.2 — Min Stack

LeetCode 155 · Medium · ★ Blind 75

The problem

Design a stack that supports push, pop, top and getMin, with every operation running in O(1).

push(-2); push(0); push(-3)
getMin()  →  -3
pop()
top()     →  0
getMin()  →  -2

The pattern

Scanning the stack for its minimum is O(n), so that is out. Keeping a single min variable fails too: when you pop the minimum, you have no idea what the new minimum is.

So the minimum has to be remembered per level, not globally. Each element needs to know what the minimum was at the moment it was pushed, because popping it must restore exactly that.

That gives the whole design: a second stack that tracks the minimum, kept in step with the first.

The solution

Python

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:      # note: <=
            self.mins.append(val)

    def pop(self) -> None:
        if self.stack.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.mins[-1]

TypeScript

class MinStack {
  private stack: number[] = [];
  private mins: number[] = [];

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

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

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

Only values that are new minima go onto the second stack, so it stays small when the data is mostly increasing. Popping removes from mins only when the value leaving was the current minimum.

The <= that everybody gets wrong

Push 2, then 2 again. With < instead of <=, only the first 2 goes into mins. Now pop once. The value popped is 2, which equals the top of mins, so mins pops too — and getMin reports whatever was underneath, even though a 2 is still on the main stack.

Using <= pushes both copies, so the first pop removes one and the second one is still there. Duplicate minima each need their own entry.

This is the bug your Report 2 recorded, and it is the single most common failure in this problem.

The simpler variant

If you would rather not think about the comparison at all, push the current minimum on every push:

def push(self, val):
    self.stack.append(val)
    self.mins.append(val if not self.mins else min(val, self.mins[-1]))

def pop(self):
    self.stack.pop()
    self.mins.pop()

Now the two stacks are always the same height, pop needs no comparison, and there is no <= to get wrong. It uses more memory in the good case and the same in the worst case. In an interview this is often the better answer — it is obviously correct, and you can offer the optimisation afterwards.

Complexity

O(1) for all four operations. O(n) space, and the second stack is at most as tall as the first.

The O(1)-space trick

There is a version that uses no second stack. Instead of storing val, store the encoded value 2 * val - currentMin whenever a new minimum arrives, and keep the current minimum in a single variable. On pop, if the stored value is below the current minimum, it is an encoded entry and the previous minimum can be recovered from it.

It works, and it is a bad idea in most languages. The encoding can overflow a fixed-width integer, and it makes the code hard to read for a saving that rarely matters. Python's unbounded integers remove the overflow risk but not the readability cost.

Mention it, then say why you would not ship it. Naming a trade honestly is worth more than the trick.

Where this goes next

The general idea is state augmentation: a data structure that carries an extra piece of information alongside its normal contents, maintained on every update.

• Max Stack — the same, mirrored.
• A queue with getMin — harder, because you remove from the opposite end to where you add. The answer is a monotonic deque, which is 4.6.6.
• A stack with getSum or getAverage — same technique, different aggregate.

The rule: if an aggregate must be available in O(1), maintain it on every update rather than computing it on demand.

What the interviewer will push on

"Why <= and not <?" Duplicate minima. Give the [2, 2] example.

"Can you use O(1) extra space?" The encoding trick, plus the honest warning about overflow.

"How would you make it thread-safe?" The two stacks must be updated together, so both operations need to be inside one lock. Updating them under separate locks would let another thread observe a mismatched pair. That is the invariant-across-two-structures problem from Chapter 2.4.

"What if you also needed getMax?" A third stack, same technique.

One thing to volunteer: say why a single min variable cannot work — popping the minimum leaves you with no way to recover the previous one. That sentence explains the whole design in one line.

Next: 4.8.3 Evaluate Reverse Polish Notation — a stack used to evaluate rather than to remember.