Min Stack

Start from brute force

The obvious approach keeps one plain stack and answers getMin with min(stack). It is correct, because the scan sees every value currently on the stack, and it needs no space beyond the stack itself: O(1) extra. But each getMin costs O(n) for n values on the stack, so a sequence of q operations can cost O(n · q); with 10⁵ pushes followed by 10⁵ reads that is 10¹⁰ comparisons, and the statement requires O(1). The other tempting shortcut, a single current_min variable, is fast but wrong: after push 3, push 1, pop it still says 1, because nothing remembers what the minimum was before the 1 arrived.

The approach

A stack only changes at its top, so the minimum of everything below the top cannot change while those values stay buried. That means the minimum can be computed once, at push time, and stored with the value. The invariant is mins[i] == min(stack[0..i]) for every level i, so mins[-1] is always the minimum of the whole stack, and popping a level restores exactly the minimum that held before it was pushed.

The reference solution keeps stack and mins the same length. On "push" it appends x to stack and x if not mins else min(x, mins[-1]) to mins; the empty check covers both the first push and any push after the stack has been emptied. On "pop" it pops both lists in lockstep. "top" appends stack[-1] to out and "getMin" appends mins[-1], so every operation is a constant number of list operations. Duplicates need no special case: pushing a second 2 appends another 2 to mins, so one pop cannot lose it.

Walk through an example

Trace the first example, [["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]], watching mins mirror stack level for level.

Complexity

Optimal: O(1) time per operation, so O(q) for q operations, and O(n) space for the two parallel stacks of up to n values, plus the output. Brute force (scan on every getMin): O(n) per getMin, up to O(n · q) overall, with O(1) extra space.

Edge cases to test

• Duplicate minimums: [["push",2],["push",2],["getMin"],["pop"],["getMin"]] → [2, 2]. A space-saving variant that pushes onto mins only when x is strictly smaller loses the second 2 and has nothing left after the pop.
• Popping the minimum: [["push",3],["push",1],["pop"],["getMin"]] → [3]. The previous minimum comes back, which a single current_min variable cannot do.
• Ascending pushes: push 1, 2, 3 gives mins = [1, 1, 1], so after a pop, getMin is still 1.
• Emptying and refilling: [["push",5],["pop"],["push",7],["getMin"],["top"]] → [7, 7]. The if not mins branch starts a fresh minimum instead of comparing with a value that is gone.
• Negative values and zero: [["push",-1],["push",0],["getMin"],["top"]] → [-1, 0]. Never use 0 as an “empty” sentinel for the minimum.
• An empty-stack pop, top or getMin is ruled out by the constraints; the Python reference would raise IndexError and the TypeScript one would return undefined.

Common mistakes

• Recomputing the minimum by scanning the stack — that makes getMin O(n) instead of O(1).
• Forgetting to pop the min-stack alongside the main stack.
• Mishandling duplicate minimums — push the running min on every push (or handle ties explicitly) so a pop cannot lose the current min.
• Tracking the minimum in one variable, which cannot be restored after the minimum is popped.

Follow-ups an interviewer asks next

Can you do it with O(1) extra space?

Yes, by encoding. Keep one variable m. When pushing x below m, push 2x − m instead and set m = x; the stored value is below the new minimum, which marks it. On pop, a stored value y below m means the previous minimum was 2m − y. top returns m for a marked value. In fixed-width integers, 2x − m can overflow.

How would you save space when the minimum rarely changes?

Push onto mins only when x <= mins[-1], and pop it only when the popped value equals mins[-1]. Pushing 5, 6, 7, 8 then stores one entry in mins instead of four. The comparison must be <=, not <, or a duplicate minimum is popped away while a copy is still on the stack.

Can you build a queue that reports its minimum?

Use two min-stacks: push onto an inbox, and pop from an outbox that is refilled by moving the whole inbox over when it runs empty. The queue’s minimum is the smaller of the two stacks’ minimums. Each element moves at most once, so every operation is amortized O(1). For a fixed sliding window, a monotonic deque does the same job.

What if you also need the maximum?

Add a third parallel stack, maxs, maintained the same way with max. The idea generalizes to any aggregate that can be combined from the value below: minimum, maximum, sum, and greatest common divisor all work. A median does not, because it cannot be computed from the previous median and one new value.

Where this shows up

“Carry an auxiliary aggregate alongside the structure” is the transferable idea — it scales to a max-stack, to min/max over a sliding window (a monotonic deque), and to running statistics. Min-stack is the smallest example of augmenting a data structure so an otherwise O(n) query becomes O(1).

Reference solution

def min_stack_ops(ops):
    stack = []
    mins = []          # mins[i] = minimum of stack[0..i]
    out = []
    for op in ops:
        kind = op[0]
        if kind == "push":
            x = op[1]
            stack.append(x)
            mins.append(x if not mins else min(x, mins[-1]))
        elif kind == "pop":
            stack.pop()
            mins.pop()          # keep the two stacks in lock-step
        elif kind == "top":
            out.append(stack[-1])
        elif kind == "getMin":
            out.append(mins[-1])
    return out


print(min_stack_ops([["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]]))  # -> [3, 5, 5]

function minStackOps(ops: any[][]): number[] {
  const stack: number[] = [];
  const mins: number[] = [];        // mins[i] = min of stack[0..i]
  const out: number[] = [];
  for (const op of ops) {
    const kind = op[0];
    if (kind === "push") {
      const x = op[1] as number;
      stack.push(x);
      mins.push(mins.length ? Math.min(x, mins[mins.length - 1]) : x);
    } else if (kind === "pop") {
      stack.pop();
      mins.pop();                    // lock-step with the value stack
    } else if (kind === "top") {
      out.push(stack[stack.length - 1]);
    } else if (kind === "getMin") {
      out.push(mins[mins.length - 1]);
    }
  }
  return out;
}

console.log(minStackOps([["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]])); // -> [3,5,5]