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 Plain-English Breakdown

Think of this like keeping track of the coldest day of the week as the days go by. If someone asks "what was the coldest day so far?", you want to answer instantly (O(1)). But here is the catch: if you step backwards in time (a pop operation), you must remember what the coldest day was before the current day happened.

Constraints to note:

• Methods will always be called on non-empty stacks (you don't have to worry about popping an empty stack unless asked by the interviewer).
• Values can be negative, zero, or positive, up to 2^{31} - 1.
• Total operations can be up to 3 \times 10^4.

Brute Force Analysis

The most obvious approach is to just use a regular array (or stack) and a single min_val variable. When we push, we update min_val = min(min_val, new_val). But what happens when we pop()? If the value we just popped was the minimum, our min_val is now outdated. To find the new minimum, we would have to scan the entire remaining stack from top to bottom.

• Time Cost: O(N) for pop(), where N is the current size of the stack.
• Why it fails: If we have 30,000 items, a single pop() could take 30,000 steps. If an interviewer asks for O(1), O(N) is an automatic fail. The waste here is forgetting history—we are throwing away the knowledge of previous minimums every time we update our single variable.

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.

ELI5 Analogy: Imagine you are packing boxes into a tight storage unit. On each box, you write its contents, but you also stick a post-it note on it that says: "Of all the boxes from the floor up to this one, the heaviest is X." When you remove the top box, you also remove its post-it note. You don't have to look at all the remaining boxes to know the heaviest one left—you just read the post-it note on the new top box! This is the "aha moment": attaching the minimum to the state of the stack at that exact moment.

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.

Code Walkthrough

1. self.stack holds the actual values, while self.mins acts as our "post-it notes", holding the minimum values.
2. Push: When a new value arrives, it always goes onto self.stack. We only put it onto self.mins if self.mins is empty OR the new value is less than or equal to the current minimum (self.mins[-1]).
3. Pop: We always pop from self.stack. We check if the value we just removed from the main stack is exactly the same as the top of self.mins. If it is, that means the minimum just left the building, so we must pop it from self.mins as well.
4. Top / getMin: These just peek at the last element of their respective arrays.

Hand Trace

Let's trace push(5), push(2), push(2), pop(), getMin():

Operation	stack	mins	getMin()	Explanation
push(5)	[5]	[5]	5	5 is first, goes to both.
push(2)	[5, 2]	[5, 2]	2	2 <= 5, so it goes to mins.
push(2)	[5, 2, 2]	[5, 2, 2]	2	2 <= 2, MUST push to mins too.
pop()	[5, 2]	[5, 2]	2	Popped 2 matches top of mins, pop mins.

If we didn't push the second 2 into mins (using < instead of <=), the pop() would have removed the only 2 from mins, leaving 5 as the minimum, which is wrong because there's still a 2 in the main stack!

Edge Cases Handled

• Pushing elements in strictly ascending order: [1, 2, 3, 4]. Only 1 goes into mins. This saves space compared to pushing onto mins every single time.
• Negative numbers: Worked flawlessly because regular integer comparison handles negatives naturally.
• Popping the only minimum: mins is perfectly synced, so removing the minimum safely exposes the previous minimum underneath it.

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.

Derivation:

• Time Complexity: O(1) for all methods. Let's trace it: append() and pop() on a Python list (or TS array) happen at the end of the array, requiring no shifting of elements. They are constant time operations. Looking up [-1] is an immediate index access, costing O(1). No loops exist anywhere in our code.
• Space Complexity: O(N). We allocate extra memory for the mins array. In the absolute worst-case scenario (e.g., pushing elements in strictly descending order like 5, 4, 3, 2, 1), every single element is a new minimum and goes into mins. Therefore, we store up to N elements in mins, making the extra space proportional to N.

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.

"What if we were constrained on memory and couldn't afford O(N) worst-case space?" You can mention storing pairs (value, count) in the mins stack. If the minimum 2 is pushed three times, instead of [..., 2, 2, 2], mins stores [..., (2, 3)]. When popping, if the value matches the top of mins, you decrement the count. Only when the count hits 0 do you actually pop the pair. This optimizes space heavily when there are many duplicate minimums.

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