Design a stack that returns its minimum in O(1) — interview question

Write a class MinStack with these operations, each running in O(1) time:

push x: put x on top.
pop: remove the top element.
top: print the top element.
min: print the smallest element currently in the stack.

If pop, top or min is called on an empty stack, print EMPTY (for pop, print it only when the stack is empty; a successful pop prints nothing).

Constraints

1 ≤ q ≤ 10^5
−10^9 ≤ x ≤ 10^9

Input and output

Input: First line: q. Then q lines, each an operation as above.
Output: One line for every `top` and `min`, and for every `pop` on an empty stack.

Examples

Input 1

8
push 5
push 2
push 7
min
pop
pop
min
top

Output

2
5
5

The minimum is 2 until 2 is popped, then it is 5 again.

Input 2

3
top
push -4
min

Output

EMPTY
-4

top on an empty stack prints EMPTY.

Show hints

Keep a second stack. Its top is always the minimum of everything currently stored.
When you push x, push min(x, current minimum) onto the second stack as well.

Show the explanation

Two parallel stacks. vals stores the values. mins stores, at the same depth, the minimum of everything from the bottom up to that depth.

push(x): push x onto vals, and mins.empty() ? x : min(x, mins.top()) onto mins.
pop(): pop both stacks.
top(): vals.top().
getMin(): mins.top().

Every operation is O(1). After a pop, the previous minimum is already waiting underneath, so nothing has to be recomputed. The cost is O(n) extra memory. A common optimisation pushes onto mins only when x <= mins.top(), and pops it only when the value being removed equals mins.top(). The <= matters for duplicates.

C++ notes

std::stack<T> is a container adaptor. It uses std::deque<T> by default and exposes only push, pop, top, empty and size.
pop() returns void. Read top() first if you need the value.
Calling top() or pop() on an empty std::stack is undefined behaviour, so the class must check empty(). Interviewers watch for this.
Keep the data members private and expose only the operations. That is the encapsulation half of the question.

Original UniCircle question. Last reviewed 22 Oct 2026.