Min Stack: O(1) Minimum with Two Stacks

LeetCode's Min Stack (problem 155) asks you to design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time. It is rated medium, and it shows up in interviews more often than you would expect. The trick is not complicated once you see it, but it is the kind of thing that trips people up when they have to implement it from scratch under time pressure.

The problem

Design a stack that supports the following operations:

• push(val) pushes an element onto the stack
• pop() removes the element on top of the stack
• top() gets the top element
• getMin() retrieves the minimum element in the stack

All operations must run in O(1) time.

stack = MinStack()
stack.push(5)
stack.push(3)
stack.push(7)
stack.getMin()  # returns 3
stack.pop()     # removes 7
stack.getMin()  # still returns 3
stack.pop()     # removes 3
stack.getMin()  # now returns 5

The first three operations are just a normal stack. The challenge is getMin(). A regular stack has no idea what its minimum is without scanning every element, which is O(n). How do you make it O(1)?

Why a single stack is not enough

Your first instinct might be to track a single min_val variable alongside the stack. When you push something smaller, update it. That handles pushes fine.

But what happens when you pop? If you pop the current minimum, what is the new minimum? You would have to scan the entire stack to find out. That is O(n), which breaks the requirement.

You need a way to "remember" what the minimum was before the current minimum was pushed. That is the core insight: you need a history of minimums, not just the current one.

And what data structure gives you a history with last-in-first-out access? A stack.

The two-stack approach

Keep two stacks side by side:

1. Main stack: holds every value, just like a normal stack.
2. Min stack: tracks the running minimum. Its top is always the current minimum of the main stack.

The rules are simple:

• push(val): always push to the main stack. If the value is less than or equal to the min stack's top (or the min stack is empty), push it to the min stack too.
• pop(): always pop from the main stack. If the popped value equals the min stack's top, pop the min stack too.
• getMin(): just return the top of the min stack. O(1).

That is it. The min stack mirrors the main stack but only grows when a new minimum (or duplicate minimum) appears, and only shrinks when that minimum gets removed.

Step-by-step walkthrough

Let's trace through a sequence of operations: push(5), push(3), push(7), push(1), getMin(), pop(), getMin(), pop(). Watch how the two stacks stay in sync.

The key thing to notice: when we pop 1 in step 6, the min stack "remembers" that 3 was the previous minimum. We never had to scan the main stack to figure that out. That is why getMin is O(1) at every point.

The code (two-stack approach)

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

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

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

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

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

That is the entire solution. Let's walk through the logic:

1. push: append to the main stack unconditionally. If val is a new minimum (or ties the current one), also append to min_stack.
2. pop: pop from the main stack. If the popped value matches the top of min_stack, pop from min_stack too, because that minimum is no longer in the main stack.
3. top: peek at the main stack.
4. getMin: peek at the min stack.

Every operation is a constant-time stack operation. No loops, no scans.

The single-stack approach (tuples)

There is an alternative that uses only one stack. Instead of storing raw values, store (value, current_min) tuples. Each entry remembers what the minimum was at the time it was pushed.

class MinStack:
    def __init__(self):
        self.stack = []  # each entry is (val, current_min)

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = min(val, self.stack[-1][1])
            self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

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

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

This is arguably simpler. Every push stores the minimum at that point in time. When you pop, the previous entry still has the previous minimum baked in. No second stack needed.

The trade-off: the two-stack approach saves space when the minimum changes infrequently (the min stack stays small). The tuple approach always uses 2x storage per element. In the worst case they are the same, but the two-stack version can be more memory-efficient in practice.

Complexity analysis

Time: O(1) per operation. push, pop, top, and getMin each do a constant number of stack operations (append, pop, peek). No loops.

Space: O(n) total for n elements. In the two-stack approach, the min stack can hold up to n elements in the worst case (if every pushed value is smaller than the previous). In the tuple approach, each of the n entries stores two values.

Both optimized approaches trade a small amount of extra space for O(1) getMin. The naive approach is the same space but O(n) getMin.

Common mistakes

A few things to watch for when implementing min stack:

1. Using < instead of <= when pushing to the min stack. If you push the same minimum value twice and only push it to the min stack once, the first pop of that value will remove the min stack entry, and the second copy in the main stack will have no corresponding minimum tracked.

2. Forgetting the empty check on the min stack. The very first push always goes to both stacks. If you skip the not self.min_stack guard, you will crash trying to access min_stack[-1] on an empty list.

3. Using == with floating point values. LeetCode 155 uses integers, so this is fine. But if you ever adapt this pattern for floats, equality comparison can bite you. Stick to integers or use a count-based approach for floats.

4. Popping from the min stack when the values do not match. Only pop from the min stack when the popped value equals the min stack's top. If you always pop from both stacks, you will lose track of the minimum.

The building blocks

This problem is built on one core building block:

Stack-based parsing

The idea of maintaining auxiliary state alongside a stack, where pushing and popping the main data triggers synchronized updates to the auxiliary state. In min stack, the "auxiliary state" is the min stack itself. Every push potentially updates the tracked minimum, and every pop potentially restores the previous minimum.

This push-and-track pattern appears in many other problems:

• Max Stack: same idea, but track the maximum instead of minimum
• Stack with increment operation: track offsets that apply lazily to the bottom k elements
• Frequency Stack: maintain a frequency map and a stack-of-stacks grouped by frequency

The core principle is always the same: when you need to answer a query about the current state of a stack in O(1), maintain a parallel data structure that stays in sync with push and pop operations.

Edge cases

Before submitting, make sure your solution handles:

• Duplicate minimums. push(2), push(2), pop(). After the pop, getMin should still return 2. This is the most common failure case.
• Single element. push(1), getMin() should return 1. pop(), then no more calls. Simple but worth verifying.
• Descending order. push(5), push(4), push(3), push(2), push(1). The min stack grows to 5 elements, exactly mirroring the main stack. Every pop removes from both.
• Ascending order. push(1), push(2), push(3), push(4), push(5). The min stack has only one element (1). Only the final series of pops touches the min stack.
• Negative numbers. push(-2), push(0), push(-3). getMin returns -3. The algorithm handles negatives with no special cases.

The two-stack solution handles all of these without any conditional branches beyond the ones already in push and pop.

From understanding to recall

You understand the two-stack trick now. It makes total sense. But can you write the push method correctly three weeks from now without looking anything up? Will you remember the <= instead of <? Will you remember to check if the min stack is empty before comparing?

These are small details, but they are exactly the kind of thing that causes bugs under interview pressure. The solution is only about 20 lines of code, but every line matters. The <= in push, the == check in pop, the separate min stack. Miss any one of them and the solution breaks on certain inputs.

Spaced repetition drills fix this. You write the min stack implementation from scratch at increasing intervals. First after a day, then three days, then a week. Each repetition cements the details until the <= and the dual pop are automatic. That is the difference between "I know how min stack works" and "I can implement min stack correctly in two minutes."

Related posts

• Valid Parentheses - The classic stack problem for bracket matching, using the same stack-based parsing building block
• Daily Temperatures - Another stack problem where auxiliary tracking (a monotonic stack) provides O(1) access to information that would otherwise require scanning

CodeBricks breaks the min stack pattern into its reusable pieces and drills them individually. You type the two-stack implementation from scratch each time, building the muscle memory so that when you see LeetCode 155 or any "design a data structure" problem in an interview, the code flows without hesitation.