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 returns to its previous value when the element that set it is popped.
• push(5), push(7) → getMin() = 5; pop() → getMin() = 5. Popping a non-minimum leaves the minimum unchanged.
• push(1), push(1), pop() → getMin() = 1. With 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 does not satisfy 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 rule it out: the problem requires O(1) getMin. An O(n) getMin fails that design requirement, and at 3·10^4 operations a getMin-heavy workload performs on the order of 10^8 comparisons.

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 store a snapshot per element. Push (val, min_so_far); the minimum in the top pair is the minimum of the whole stack, and a pop restores the previous minimum with no extra work.

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 no recomputation: 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 largely redundant, because the running minimum only changes when a new value is <= the current minimum. Keep a second stack holding just those record-setting values, and pop it only when the departing element equals its top. The operations stay O(1), and the min stack stays small 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, with a smaller auxiliary stack.

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, and so on) queryable in O(1) on a stack, store the aggregate’s running value with the elements so it is restored automatically on pop. In a LIFO structure, every state you can return to is a state you have already seen, so store it instead of recomputing it. The same idea of augmenting each stack frame with a summary appears in max-stack, stack-based sliding-window problems, and monotonic-queue designs.