DSAPrep
MediumStack

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element, all in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]\n[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin() returns -3; minStack.pop(); minStack.top() returns 0; minStack.getMin() returns -2.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
View original on LeetCode ↗

Naive (Scan for Min)

Time push/pop/top: O(1), getMin: O(n)Space O(n)

The obvious design is a plain stack for push/pop/top. For getMin, just scan every element currently on the stack and take the smallest.

class MinStack:
    def __init__(self):
        self.stack = []


    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)

This is correct, but getMin is O(n) because it has no memory of past minimums — it recomputes from scratch every call. The problem explicitly requires every operation to be O(1), so this fails the constraint even though it passes correctness.

Two Parallel Stacks

OptimalTime O(1) for every operationSpace O(n)

The key idea: instead of computing the minimum on demand, track it incrementally as items are pushed. Keep a second stack, min_stack, running in lockstep with the main stack. min_stack[i] holds “the minimum of all elements from the bottom of the stack up to and including position i.”

Every time we push a value, we push min(val, current_min) onto min_stack — so the top of min_stack is always the minimum of everything currently on the main stack. Every time we pop, we pop from both stacks together, which correctly “forgets” the minimum contributed by the popped element and reveals what the minimum was before it was pushed.

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


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

Tracing the statement example (push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()) — watch the two lanes keep matching heights, and exactly what the top of min_stack does when -3 is pushed and then popped:

init

stack

empty

min_stack

empty

invariant: min_stack[i] = min(stack[0..i]) — getMin() reads its top

1 / 8
currentseenresultcomparingdiscarded

Two lanes keep the same height: `stack` stores values; `min_stack` records the smallest value from the bottom up to each row i. getMin reads the top of `min_stack`, captured in advance. Both lanes start empty.

Notice how after popping -3, min_stack correctly reverts to showing -2 as the minimum — it never had to search, because that value was already recorded when 0 was pushed. Every operation only touches the top of one or both stacks, so push, pop, top, and getMin are all O(1) time. Space is O(n) for keeping the second stack alongside the first — a constant-factor overhead over a plain stack, not a complexity trade-off.