Min Stack

mediumStack18 stepsJava · Python · C++

Support push, pop, top and getMin in O(1). Keep a second stack where each entry is the minimum of everything at or below that level. Pushing records min(x, currentMin); popping removes both tops together.

▶ Watch the animated trace

Traced input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() → [null, null, null, -3, null, 0, -2]. Original problem: neetcode.io/problems/minimum-stack

Complexity

BestO(1)

AverageO(1)

WorstO(1)

SpaceO(n)

Every operation is O(1); the extra stack doubles the space.

Key idea

The minimum only changes when you push or pop, so remember it per level.
mins.peek() is always the minimum of the whole stack.
Push min(x, mins.peek()) so both stacks stay the same height.

Common mistakes

Storing a single min variable fails after popping the minimum.
Only pushing onto mins when x is smaller works, but then pops must compare values; duplicates make that fragile.
Using Integer == instead of .equals on boxed values above 127.

Solution

Java

class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    void push(int x) {
        stack.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }

    void pop() {
        stack.pop();
        mins.pop();
    }

    int top() {
        return stack.peek();
    }

    int getMin() {
        return mins.peek();
    }
}

Python

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

    def push(self, x: int) -> None:
        self.stack.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

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

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

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

C++

class MinStack {
    stack<int> st, mins;

public:
    void push(int x) {
        st.push(x);
        mins.push(mins.empty() ? x : min(x, mins.top()));
    }

    void pop() {
        st.pop();
        mins.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return mins.top();
    }
};

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Duplicate minimums Each level stores its own minimum, so popping one 1 leaves the other.	`push(1), push(1), pop(), getMin()`	`[null, null, null, 1]`
Increasing pushes The minimum stays 1 at every level.	`push(1), push(2), push(3), getMin()`	`[null, null, null, 1]`
Extreme values No arithmetic on values, so no overflow (unlike the "store differences" trick).	`push(2147483647), push(-2147483648), getMin()`	`[null, null, -2147483648]`