Min Stack

Problem

Design a stack that, in addition to the usual operations, can report its minimum element at any time. Implement a class MinStack with:

• push(val) — put val on top of the stack
• pop() — remove the top element
• top() — return the top element without removing it
• getMin() — return the smallest element currently in the stack

Every operation, including getMin, must run in O(1) time. pop, top, and getMin are only ever called on a non-empty stack.

Examples

• push(-2), push(0), push(-3) → getMin() = -3; then pop() → top() = 0, getMin() = -2 — the minimum “rewinds” when the element that held it is popped.
• push(5), push(7) → getMin() = 5; pop() → getMin() = 5 — popping a non-minimum leaves the minimum untouched.
• push(1), push(1), pop() → getMin() = 1 — duplicate minima: removing one copy must not lose the other.

Constraints

• -2^31 <= val <= 2^31 - 1
• Up to 3 * 10^4 operations total

The operation count is small, but the O(1)-per-operation requirement is the real constraint — a getMin that scans the stack is O(n) and misses the point of the problem.

Think about it first

TL;DR

Store the running minimum alongside every element (paired stack) — O(1) time for every operation, O(n) space.

Approach 1 — Brute force (naive design)

This is a design problem, so there is no algorithmic brute force — the naive design is a plain list whose getMin rescans everything.

class MinStack:
    def __init__(self) -> None:
        self.stack: list[int] = []

    def push(self, val: int) -> None:
        self.stack.append(val)

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

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

    def getMin(self) -> int:
        return min(self.stack)

Complexity: push/pop/top O(1), but getMin is O(n).

Why the constraints kill it: the problem explicitly demands O(1) getMin; with 3·10^4 operations an all-getMin workload does ~4.5·10^8 comparisons, and more importantly it fails the stated design requirement.

Approach 2 — Pair each element with the minimum below it

The insight: the stack’s minimum after a pop is exactly what it was before the popped element was pushed — minima history unwinds in LIFO order, so snapshot it per element. Push (val, min_so_far); the top pair always knows the whole stack’s minimum, and popping automatically “rewinds” it.

class MinStack:
    def __init__(self) -> None:
        self.stack: list[tuple[int, int]] = []   # (value, min of stack up to here)

    def push(self, val: int) -> None:
        if self.stack:
            current_min = min(val, self.stack[-1][1])
        else:
            current_min = val
        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]

Walkthrough of the first example — push(-2), push(0), push(-3), getMin(), pop(), top(), getMin():

The old minimum -2 reappears with zero work: it was stored with the element below.

Complexity: all four operations O(1); O(n) space — one extra integer per element.

Approach 3 — Two stacks, minima stored only when they change

The insight: the snapshot column above is hugely redundant — the running minimum only changes when a new value is <= the current minimum. Keep a second stack holding just those “record-setting” values; pop it only when the departing element equals its top. Same O(1) operations, but the min stack stays tiny when data arrives in random or increasing order.

class MinStack:
    def __init__(self) -> None:
        self.stack: list[int] = []
        self.mins: list[int] = []       # non-strictly decreasing record minima

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.mins or val <= self.mins[-1]:
            self.mins.append(val)       # note: <= handles duplicate minima

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

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

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

Walkthrough (same example): pushes put -2, 0, -3 on the main stack, while mins records only -2, -3 (0 is not a new minimum). getMin → -3. pop removes -3, which equals mins top, so mins shrinks to -2. top → 0, getMin → -2. Same answers, smaller sidecar.

Complexity: all operations O(1); O(n) space worst case (strictly decreasing pushes), typically far less.

Common pitfalls

• Duplicate minima: in Approach 3, pushing with < instead of <= breaks push(1), push(1), pop(), getMin() — the second 1 records nothing, then popping it (equal to mins top, if you also pop there) or popping the first later desynchronizes the two stacks. <= on push paired with == on pop is the consistent pair.
• A single self.min variable with no history — works until the minimum is popped, then requires an O(n) rescan; the whole problem is about keeping the history of minima.
• Popping mins unconditionally in Approach 3 — only pop it when the departing value equals its top.
• Storing indices of minima — valid but fiddly; values are enough because comparisons, not positions, drive the rewind.

Pattern takeaway

To make an aggregate (min, max, gcd, …) queryable in O(1) on a stack, store the aggregate’s running value with the elements so it rewinds automatically on pop — LIFO structure means every state you might return to is a state you already saw, so snapshot it instead of recomputing. This “augment each stack frame with a summary” trick reappears in max-stack, stack-based sliding-window problems, and monotonic-queue designs.