Min Stack: Get the Minimum in O(1) With a Second Stack

"Design a stack that supports push, pop, top, and retrieving the minimum element in constant time." A plain stack already does three of those in O(1). The fourth looks like it needs a scan, and the trick is to notice that a stack only ever changes at one end, so the minimum can be remembered instead of recomputed.

The problem it solves

Implement push(x), pop(), top() and get_min(), each in O(1) time. get_min() returns the smallest value currently in the stack. Calls to pop, top and get_min are only made on a non-empty stack.

Two quick answers both fail:

• Scan on demand. min(items) is correct but O(n) per call.
• Keep one variable, current_min. Push is easy: compare and update. But when the minimum is popped, the variable has no idea what the previous minimum was, and finding it means a scan again.

The second answer is the interesting failure. It stores the right thing, just not enough of it.

The intuition

A stack is a history: every level sits on top of everything pushed before it, and popping only ever undoes the most recent push. So the minimum at any moment depends only on the values at or below the top.

That suggests storing, beside each value, the minimum of everything at or below it. Call it the shadow stack, mins. When x is pushed, the new entry is min(x, mins[-1]), one comparison. When a value is popped, its shadow entry is popped with it, and whatever is now on top of mins is, by construction, the minimum of what is left. Nothing is ever recomputed; the old answer was saved at the moment it was true.

For 5, 2, 7, 1 the shadow stack is 5, 2, 2, 1. Pop the 1 and the top of mins is 2 again, which is correct, because 2 was the minimum before 1 arrived.

Watch it run

The animation pushes the lesson's 5, 2, 7, 1 onto two piles side by side. Watch the right pile: when 7 arrives it is not smaller, so the pile repeats 2. Reading min() then touches a single chip. The last frames pop the 1 from both piles at once, and the old minimum is simply on top again.

The code

The two-stack version. mins[i] is the minimum of items[0] through items[i]:

class MinStack:
    def __init__(self):
        self.items = []
        self.mins = []                 # mins[i] = min(items[0..i])

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

    def pop(self):
        self.mins.pop()
        return self.items.pop()

    def top(self):
        return self.items[-1]

    def get_min(self):
        return self.mins[-1]

s = MinStack()
for x in [5, 2, 7, 1]:
    s.push(x)
print(s.get_min(), s.mins)             # 1 [5, 2, 2, 1]
s.pop()
print(s.get_min(), s.top())            # 2 7

A leaner variant pushes onto mins only when the minimum could change, and pops from it only when the value leaving equals the current minimum. On inputs that rarely set a new minimum, the shadow stack stays short:

class LeanMinStack:
    """Pushes onto mins only when the minimum could change."""
    def __init__(self):
        self.items, self.mins = [], []

    def push(self, x):
        self.items.append(x)
        if not self.mins or x <= self.mins[-1]:   # <=, not <
            self.mins.append(x)

    def pop(self):
        x = self.items.pop()
        if x == self.mins[-1]:
            self.mins.pop()
        return x

    def get_min(self):
        return self.mins[-1]

lean = LeanMinStack()
for x in [5, 6, 7, 8, 2, 9]:
    lean.push(x)
print(lean.mins)                       # [5, 2]

The <= matters. With a strict <, a second copy of the minimum is not recorded, and popping one copy removes the only record while the other copy is still in the stack:

class BrokenMinStack(LeanMinStack):
    def push(self, x):
        self.items.append(x)
        if not self.mins or x < self.mins[-1]:    # strict: drops duplicates
            self.mins.append(x)

b = BrokenMinStack()
for x in [2, 2]:
    b.push(x)
b.pop()
print(b.items, b.mins)                 # [2] []

Both correct versions against a plain list and Python's min, over 2,000 random sequences of pushes and pops. The values are drawn from a small range so duplicates of the minimum are common:

import random

random.seed(6)
ok = True
for _ in range(2000):
    stacks = [MinStack(), LeanMinStack()]
    reference = []
    for _ in range(random.randint(1, 40)):
        if reference and random.random() < 0.4:
            expected = reference.pop()
            ok &= all(st.pop() == expected for st in stacks)
        else:
            x = random.randint(-3, 3)          # small range: many duplicates
            reference.append(x)
            for st in stacks:
                st.push(x)
        if reference:
            ok &= all(st.get_min() == min(reference) for st in stacks)
print(ok)                              # True

The complexity

Every operation does a constant amount of work: one or two appends or pops on Python lists, plus at most one comparison. So push, pop, top and get_min are all O(1) time, amortised over list growth.

Space is O(n) extra for the two-stack version, one shadow entry per value. The lean version is still O(n) in the worst case, a strictly decreasing input records every value, but it can be much smaller in practice. A third common layout stores (value, current_min) pairs in a single list; it is the two-stack version with the columns zipped together.

Where it goes wrong

• One variable instead of a history. A single current_min cannot answer "what was the minimum before this one?" after a pop.
• Strict < in the lean version. Duplicates of the minimum must each be recorded, or the first pop of a duplicate erases the minimum too early, as shown above.
• Popping only one stack. In the two-stack version the stacks must stay the same height. A pop that forgets mins leaves a stale minimum behind.
• Comparing by identity. In languages with boxed integers, comparing the popped value with mins[-1] by reference instead of by value can fail for equal numbers. Python's == compares values, which is what the lean version needs.

How to say it in an interview

"A stack only changes at the top, so the minimum at each level can be saved when that level is pushed. I keep a second stack where each entry is the minimum of everything at or below it: push appends min(x, mins[-1]), pop removes from both. Every operation is O(1), at the cost of O(n) extra space. To save space I can push to the min stack only when x is at most the current minimum, and that test has to be <=, or a duplicate minimum gets lost on the first pop."

The same "carry the answer with the data" idea powers the monotonic stack, and its queue cousin keeps a window's maximum in the sliding window maximum lesson.