Min Stack

Min Stack asks you to support the usual stack operations plus a getMin() — and make all of them O(1). The trick is a classic: when one stack can't answer fast enough, keep a second stack alongside it.

The slow way first

The lazy version: keep one normal stack and, whenever someone calls getMin(), scan the whole stack to find the smallest value. That makes getMin() O(n). For a stack used in a hot loop, that is unacceptable — and the whole point of the problem is to avoid it.

The question to ask: can I know the minimum without looking? If I always had the answer ready before the call, getMin() would be a single peek.

The idea: a parallel min stack

Keep a second stack, mins, that mirrors the main one. Its top is always the minimum of everything currently in the main stack.

• On push(x): the new running minimum is min(x, current min). Push x to the main stack and that running minimum to mins.
• On pop(): pop both stacks. Removing the top of mins automatically restores the previous minimum.
• getMin() is just mins[-1] — one peek, O(1).

The key insight: by storing the minimum at each level, popping naturally "uncovers" the previous minimum. We never recompute anything.

Walk through it

Step through the animation. We push 5, 3, 7, 2. The min stack on the right records the running minimum at each height: 5, then 3, then 3 again (7 did not beat 3), then 2. When we pop() the 2, both stacks drop their top and getMin() is back to 3 for free — no scanning.

Pseudocode

push(x):
    cur_min = x if mins is empty else min(x, top of mins)
    main.push(x)
    mins.push(cur_min)
 
pop():
    main.pop()
    mins.pop()        # drop in lockstep -> previous min is uncovered
 
top():    return top of main
getMin(): return top of mins

The Python solution

class MinStack:
    def __init__(self):
        self.stack = []       # (value, min_so_far) pairs
        self.mins = []        # running minimum
 
    def push(self, x):
        cur_min = min(x, self.mins[-1]) if self.mins else x
        self.stack.append(x)
        self.mins.append(cur_min)
 
    def pop(self):
        self.stack.pop()
        self.mins.pop()
 
    def top(self):
        return self.stack[-1]
 
    def get_min(self):
        return self.mins[-1]

• self.mins[-1] is the live minimum; we read or update it in O(1) with no loop.
• On push, cur_min = min(x, self.mins[-1]) carries the smallest-so-far up to the new top.
• On pop, popping self.mins in lockstep means the previous minimum is already sitting on top — nothing to recompute.
• top() and get_min() are plain peeks of the two stacks.

Complexity

We spend O(n) extra space on the parallel min stack to buy O(1) on every operation. That space-for-time trade is the heart of the problem.

When this pattern shows up

Practice