Min Stack

This is a design problem, not an algorithm problem: you build a small class with four methods. It shows up often because it tests one idea that is useful far beyond stacks — when an answer depends on history and must be instant, store the answer alongside the history instead of recomputing it.

The class is short. The discussion around it — why the obvious fix fails, what the space costs, how ties behave — is what the interviewer is grading.

The problem

Design a stack of integers with four operations, each running in O(1) time: push(value), pop() (removes the top), top() (returns the top) and get_min() (returns the smallest value currently in the stack).

Example, one call per line:

push(-2)push(0)push(-3)get_min()  -> -3pop()                 # removes -3top()      -> 0get_min()  -> -2      # -3 is gone, so the minimum goes back to -2

Constraints: values fit in 32 bits; up to 3 × 10⁴ calls in total; pop, top and get_min are only called on a non-empty stack.

Clarifying questions

• Can values repeat? Yes, including repeats of the minimum. This matters for one of the designs.
• What should pop on an empty stack do? It will not be called; say you would raise an error in real code.
• Does pop return the value? Not required; return nothing.
• Is O(1) amortised acceptable? Yes; Python's list append is amortised O(1).

Approach 1: the simple way

Keep a normal list and compute the minimum when asked.

1class MinStackSlow:2    """get_min scans every value: O(n)."""34    def __init__(self) -> None:5        self.items: list[int] = []67    def push(self, value: int) -> None:8        self.items.append(value)910    def pop(self) -> None:11        self.items.pop()1213    def top(self) -> int:14        return self.items[-1]1516    def get_min(self) -> int:17        return min(self.items)

Time: O(1) for push, pop and top; O(n) for get_min. Space: O(n).

With 10⁴ values on the stack and 10⁴ calls to get_min, that is 10⁸ comparisons, and the problem demands O(1).

The obvious fix is one variable, self.smallest, updated on each push. Push is easy: smallest = min(smallest, value). Pop is the problem. In the example, after pop() removes -3, the variable still says -3. The new minimum is -2, but to know that you would have to scan everything below — back to O(n). One number cannot remember what the minimum was before each push.

The key insight

The minimum of the stack depends only on what is in it, and a stack only changes at the top. So the minimum when some item is on top is fixed forever at the moment that item is pushed: it is the smaller of the item and the minimum below it. Nothing that happens later can change it, because anything pushed later is removed before this item is.

So store, with every item, the minimum of that item and everything below it. Then:

• get_min reads the stored minimum of the top item: O(1).
• pop removes the top item, and the item below it already carries its own minimum. The old minimum comes back for free, with no scan.

This is an augmented stack: each entry carries a summary of the stack beneath it.

Why not a heap, which is built to return the minimum? Because a heap and a stack disagree about which item leaves next. pop must remove the most recent item, which can be anywhere in the heap. Finding and removing it costs O(n), or O(log n) with extra bookkeeping — still not O(1). The stack already knows which item leaves next, so it only has to remember one extra number per item.

Approach 2: store the minimum with each value

1class MinStack:2    """Stack with push, pop, top and get_min, all O(1)."""34    def __init__(self) -> None:5        self.items: list[tuple[int, int]] = []   # (value, minimum of this item and all below)67    def push(self, value: int) -> None:8        smallest = value if not self.items else min(value, self.items[-1][1])9        self.items.append((value, smallest))1011    def pop(self) -> None:12        self.items.pop()                         # the minimum below comes back with it1314    def top(self) -> int:15        return self.items[-1][0]1617    def get_min(self) -> int:18        return self.items[-1][1]

Dry run on the example (bottom → top, each entry is (value, min)):

After the pop, the top entry is (0, -2), which has remembered since it was pushed that the minimum below it was -2.

Time: O(1) for every operation. Space: O(n), with two numbers per item.

Approach 3: a second stack for minimums only

If new minimums are rare — say, prices that mostly rise — storing a minimum with every item wastes space. Instead keep a second stack that records a value only when it is a new minimum or ties the current one:

1class MinStackTwoStacks:2    """Second stack records only values that are a new minimum (or tie it)."""34    def __init__(self) -> None:5        self.items: list[int] = []6        self.mins: list[int] = []78    def push(self, value: int) -> None:9        self.items.append(value)10        if not self.mins or value <= self.mins[-1]:   # <= so duplicates of the minimum count11            self.mins.append(value)1213    def pop(self) -> None:14        if self.items.pop() == self.mins[-1]:15            self.mins.pop()1617    def top(self) -> int:18        return self.items[-1]1920    def get_min(self) -> int:21        return self.mins[-1]

The same example, traced on both stacks:

When the popped value equals the current minimum, it was recorded on mins when it was pushed, so pop it there too. The <= is essential: push 1, push 1, pop. With <, only the first 1 was recorded, the pop removes that record, and mins is empty while a 1 is still on the stack.

Same O(1) time. Space is O(n) in the worst case (a falling sequence records everything), but much less when new minimums are rare. Put numbers on it: a million rising prices cost Approach 2 two million stored integers, and Approach 3 about one million and one. A million falling prices cost both about two million. Say which case you expect before choosing. Both designs were checked against MinStackSlow on 3,000 random operations each.

Edge cases

• Repeated minimum: push 2, push 2, pop — the minimum must still be 2. Approach 2 handles it naturally; Approach 3 needs the <=.
• Negative numbers: nothing special; there is no sentinel value like 0 or -1 to go wrong.
• One item: its stored minimum is itself.
• Minimum at the bottom forever: get_min returns it from the top entry without looking down.

Follow-ups

• "Save space." Use Approach 3, and note it saves space only when new minimums are rare. (Another trick stores the difference from the current minimum in one stack; it saves the second stack but is easy to get wrong with overflow in fixed-width languages.)
• "Max stack with pop_max." Removing from the middle breaks the stack model. Use a heap with lazy deletion, or a sorted structure plus a doubly linked list: O(log n) per operation.
• "A queue with get_min." Build a queue from two min-stacks (push to one, pop from the other, moving items across when the second is empty). Every operation is amortised O(1), and it solves sliding-window minimum.