Min Stack

PracticeNeetCode ↗LeetCode ↗

Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time.

Example

Input push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Output -3, then 0, then -2

Key Pointers

A single stack alone can't answer getMin() in O(1), since the minimum could be buried anywhere below the top.
Run a second stack alongside the first that tracks the minimum-so-far at each depth, moving in lockstep with pushes and pops.
On every push, push min(new value, current min) onto the min-stack — its top is then always the current minimum.

Step-by-Step Analysis

Maintain two stacks: stack for the real values, min_stack for running minimums.
On push(val): push val onto stack; push min(val, min_stack top) (or just val if min_stack is empty) onto min_stack.
On pop(): pop both stacks together, so they stay the same size.
getMin() reads min_stack's top; top() reads stack's top — both O(1).

Complexity

Time: O(1) for every operation — Space: O(n)

Code

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

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

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

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

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

Code Explanation

How the solution above works, piece by piece.

Two stacks: stack holds the values, min_stack holds "the minimum so far" at each height.
push: append the value, and append min(val, previous minimum) to min_stack (or just val if it's the first element).
pop removes from both stacks, so the minimum automatically goes back to what it was before that push.
top reads stack[-1]; getMin reads min_stack[-1]. No searching needed.
Every operation is O(1) time; the extra stack costs O(n) space.

Visual Walkthrough

Running the example operations:

The min stack (right of each pair) has one entry per element: the minimum of everything at or below that level. Its top is always the current minimum, and popping both stacks together keeps them in sync.

just pushedcurrent minimum

Video Explanation

NeetCode — Amazon Interview Question, LeetCode 155