Min Stack

MediumStack · Design🧩 Stack LeetCode #155 ↗Updated Oct 30, 2026

Problem

Design a class MinStack that behaves like a normal integer stack (push, pop, top) and also answers getMin() — the smallest value currently on the stack. Every operation should run in O(1) time.

Inputpush(-2) push(0) push(-3)OutputgetMin() = -3

Inputpop() top() getMin()Output0, -2

-2³¹ ≤ val ≤ 2³¹-1 · pop/top/getMin only on a non-empty stack · ≤ 3·10⁴ calls · each op O(1)

Try it yourself

Java

class MinStack {
    public void push(int val) {
        
    }

    public void pop() {
        
    }

    public int top() {
        
    }

    public int getMin() {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A stack only changes at the top, so the minimum below any element never changes while that element is on the stack. Record the “min so far” at push time and restore it at pop time.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForcePlain Stack, Scan for Min

Time O(1) push/pop/top, O(n) getMinSpace O(n)

Keep an ordinary stack and compute the minimum on demand by iterating over every element. Correct, because the stack always holds exactly the live values.

Java

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

    public void push(int val) { stack.push(val); }

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

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

    public int getMin() {
        int min = Integer.MAX_VALUE;
        for (int x : stack) min = Math.min(min, x);
        return min;
    }
}

Simplest possible, but getMin is linear — violates the O(1) requirement.

BetterStack of (value, minSoFar) Pairs

Time O(1) all opsSpace O(n)

Push each value together with min(val, previous min). The pair on top always knows the minimum of everything beneath it, and popping automatically “restores” the older minimum.

Java

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();

    public void push(int val) {
        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, min});
    }

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

    public int top() { return stack.peek()[0]; }

    public int getMin() { return stack.peek()[1]; }
}

All O(1), but stores a second int for every element.

OptimalSingle Stack + min Variable

Time O(1) all opsSpace O(n)

Hold the current minimum in min. Only when a value ≤ min arrives, first push the old min as a marker, then the value. Popping a value equal to min means its marker sits below it: pop that too and restore min. Extra storage is paid only when the minimum changes.

Java

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

    public void push(int val) {
        if (stack.isEmpty()) {
            min = val;
        } else if (val <= min) {
            stack.push(min);   // save the previous minimum
            min = val;
        }
        stack.push(val);
    }

    public void pop() {
        if (stack.pop() == min && !stack.isEmpty()) {
            min = stack.pop(); // restore the previous minimum
        }
    }

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

    public int getMin() { return min; }
}

O(1) everything and extra space proportional to min changes, not n.

Pro tip

stack.pop() == min is safe because min is an int (unboxing); comparing two Integers with == would break above 127.

At a glance

Level	Approach	Time	Space
Brute Force	Plain Stack, Scan for Min	`O(1) push/pop/top, O(n) getMin`	`O(n)`
Better	Stack of (value, minSoFar) Pairs	`O(1) all ops`	`O(n)`
Optimal	Single Stack + min Variable	`O(1) all ops`	`O(n)`

Common pitfalls

Using val < min instead of ≤ — duplicate minimums lose the old min on pop.
A single min field with no history — cannot recover after popping the min.
Storing val - min in an int — overflows at ±2³¹; needs long.

Interview tips

Start from the O(n) getMin scan, then ask: what does each element need to remember?
Explain why the min below an element is frozen while it is on the stack.
Offer the space trade-off: pairs (simple) vs markers only on min change.

Pattern

Augmented stack → track an aggregate (min/max) of the stack in O(1) per operation.

My notes saved in this browser