#155 Min Stack

frequently reported atBloomberg Oracle Amazon Microsoft Google Meta

the problem

In plain words

Design a stack with push(val), pop(), top() and getMin(). getMin() returns the smallest element currently in the stack. Every operation must run in O(1) time.

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

out -3, 0, -2

After popping -3 the minimum goes back to -2.

−2³¹ ≤ val ≤ 2³¹ − 1
pop, top and getMin are only called on a non-empty stack
At most 3·10⁴ calls

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack & queue design

The minimum only changes when you push or pop — and a stack only changes at the top. So remember, for each level of the stack, what the minimum was at that moment.

solutions

From brute force to optimal

A plain stack; getMin walks every element.

push/pop/top use the stack directly.
getMin loops over all items and keeps the smallest.

timeO(n) getMin, O(1) others

getMin visits every element; fails the O(1) requirement.

spaceO(n)

The stack itself.

javaScanMinStack (rename to MinStack on LeetCode)java.util.* · java.util.function.*

1class ScanMinStack {2    private final Deque<Integer> stack = new ArrayDeque<>();3 4    public void push(int val) { stack.push(val); }5    public void pop() { stack.pop(); }6    public int top() { return stack.peek(); }7 8    public int getMin() { // walks every element: O(n)9        int min = Integer.MAX_VALUE;10        for (int x : stack) min = Math.min(min, x);11        return min;12    }13}

Each entry also stores the minimum of itself and everything below it. The top entry always knows the current minimum.

push(val): min = empty ? val : min(val, top.min); push {val, min}.
pop(): pop the pair — the entry below already holds the older minimum.
top() = top.value, getMin() = top.min.

timeO(1) every operation

Each call touches only the top entry.

spaceO(n)

Two ints per entry.

javaMinStackjava.util.* · java.util.function.*

1class MinStack {2    // each entry = {value, minimum of this entry and everything below it}3    private final Deque<int[]> stack = new ArrayDeque<>();4 5    public void push(int val) {6        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);7        stack.push(new int[] {val, min});8    }9    public void pop() { stack.pop(); }               // the entry below already knows its own min10    public int top() { return stack.peek()[0]; }11    public int getMin() { return stack.peek()[1]; }12}

sim

Dry run

loading simulation…

javajava.util.* · java.util.function.*

1class MinStack {2    // each entry = {value, minimum of this entry and everything below it}3    private final Deque<int[]> stack = new ArrayDeque<>();4 5    public void push(int val) {6        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);7        stack.push(new int[] {val, min});8    }9    public void pop() { stack.pop(); }               // the entry below already knows its own min10    public int top() { return stack.peek()[0]; }11    public int getMin() { return stack.peek()[1]; }12}

A second stack only records new minimums (including ties), so it is often much shorter.

push(val): push to stack; if mins is empty or val ≤ mins.top, push val to mins too.
pop(): pop from stack; if that value equals mins.top, pop mins too.
getMin() = mins.top.

timeO(1) every operation

Each call does at most one push/pop on each stack.

spaceO(n)

Worst case (decreasing pushes) both stacks hold n items; usually mins is smaller.

javaTwoStackMinStack (rename to MinStack on LeetCode)java.util.* · java.util.function.*

1class TwoStackMinStack {2    private final Deque<Integer> stack = new ArrayDeque<>();3    private final Deque<Integer> mins = new ArrayDeque<>(); // top = current minimum4 5    public void push(int val) {6        stack.push(val);7        if (mins.isEmpty() || val <= mins.peek()) mins.push(val); // <= keeps duplicates of the min8    }9    public void pop() {10        int removed = stack.pop(); // unbox to int so == below compares values, not references11        if (removed == mins.peek()) mins.pop();12    }13    public int top() { return stack.peek(); }14    public int getMin() { return mins.peek(); }15}

in the room

How to say it in the interview

talk track

Point out that a single min variable fails: after popping the minimum, you can't recover the previous one.
Present the pair idea: "each level remembers the min at that level."
Explain why the two-stack version uses <=: duplicates of the minimum must each be recorded, or popping one would lose the other.

traps

Using < instead of <= when pushing to the min stack — push −2, −2, pop → getMin breaks.
Comparing stack.peek() == mins.peek() as two Integer objects: works for small numbers (cache), fails for 1000. Unbox to int first.

what they ask next

Follow-ups

Can you do it with O(1) extra space (no second stack)?

Yes: store differences (val − min) as long and update min when a negative difference is pushed/popped. Clever, but easy to get wrong — mention it, code the pair version.

Max Stack (LC 716) with popMax()?

popMax needs to remove from the middle: use a TreeMap<value, list of nodes> plus a doubly linked list for O(log n) per operation.

before you submit

Edge cases to test

Duplicate minimums: push 1, push 1, pop → getMin() must still be 1 (that's why the two-stack version uses <=).
Values outside −128..127, like 1000: comparing two Integers with == compares references and breaks.
Integer.MIN_VALUE and Integer.MAX_VALUE are valid values; a min-so-far that starts at MAX_VALUE must still work.

practise next