Min Stack

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

push(x) — push x onto the stack.
pop() — remove the element on top.
top() — return the top element.
getMin() — return the minimum element currently in the stack.

pop, top, and getMin are only called on a non-empty stack.

Hints

· Stuck? Reveal one nudge at a time.

getMin in O(1) means you can't scan the stack — store the minimum somewhere.

Alongside each element, remember the minimum of the stack up to that element.

Push both (min of new value and previous min) and pop both together.

Common doubts

A single min variable can't be restored when you pop the current minimum. Storing the running minimum per element lets pop reveal the previous minimum instantly.

min(x, current minimum) — so the top of mins is always the minimum of the whole stack.

Yes — store pairs (value, min-so-far), or use an encoding trick that stashes the old minimum when a new minimum is pushed. The two-stack version is the clearest.

Interview follow-ups

· What an interviewer asks next.

Keep a parallel maxes stack with max(x, previous max) — the exact mirror.

Push onto the mins stack only when a new value is <= the current min, and pop it only when the popped value equals the current min — saving space when minimums repeat rarely.

Fun facts

Min Stack is the textbook example of 'augment your structure with the query's answer'.
The same idea gives O(1) min/max over a sliding window when combined with the two-stack queue — a min-queue.

Asked at

AmazonGoogleMicrosoftBloomberg

Frequently Sometimes Occasionally

Example 1

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: -3, 0, -2
getMin returns -3, then after popping -3, top is 0 and getMin is -2.

Example 2

Input: push(1), getMin(), top()
Output: 1, 1
With one element, both getMin and top return 1.

Constraints

- -2^31 <= x <= 2^31 - 1 - At most 3 * 10^4 operations - pop/top/getMin only on a non-empty stack

getMin in O(1) is the whole challenge — you can't scan the stack each call. The trick: alongside each element, remember the minimum of the stack up to and including that element. Then the current minimum is always sitting at the top of that companion record, and it's maintained in O(1) on every push and pop.

Prerequisites

Before you start

· Concepts used directly in the solution.

Augmented stack. Storing an extra fact next to each value so a query becomes O(1).

Prefix minimum. The minimum of everything pushed so far, updated as you go.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The contract

“Must getMin be O(1)?”

Yes — scanning the stack per call would be O(n).

“Are pop/top/getMin ever called on an empty stack?”

No — only on a non-empty stack.

The ideal opening — say it like this

The hard part is O(1) getMin, so I store, next to each element, the minimum of the stack up to that point.

On push I record min(new value, previous minimum); on pop I discard both entries together.

Then getMin is just reading the top of that minimum record.

Understand the problem

Worked example — push -2, push 0, push -3, getMin, pop, top, getMin

push -2 -> st [-2],       mins [-2]
push 0  -> st [-2,0],     mins [-2,-2]
push -3 -> st [-2,0,-3],  mins [-2,-2,-3]
getMin  -> mins.top = -3
pop     -> st [-2,0],     mins [-2,-2]
top     -> 0
getMin  -> mins.top = -2

Key observations

1Aha

Store the running minimum beside each element

mins[i] = min(st[0..i]). Maintaining it on push (as min(x, mins.top)) means the current minimum is always at the top.

2Aha

Pop both stacks together

Removing an element must also remove its recorded minimum, keeping the two stacks aligned so the top of mins always reflects the current stack.

3Aha

Every operation is O(1)

push, pop, top, and getMin are all constant-time — no scanning, ever.

Summary

Key takeaway

Pair the value stack with a mins stack where each entry is the running minimum. Push both (recording min(x, prev min)), pop both, and getMin reads the top of mins. All operations O(1).

push(x): st.push(x); mins.push(min(x, mins.top or x))
pop():   st.pop(); mins.pop()
top():   return st.top()
getMin():return mins.top()