Stack with constant-time minimum

Design a stack that, besides the usual operations, returns its smallest element, with every operation in constant time.

Interface

Unless you agree on a different interface with the interviewer, assume:

• push(x: int) -> None
• pop() -> int — removes and returns the top element.
• top() -> int — the top element, without removing it.
• get_min() -> int — the smallest element currently in the stack.
• pop, top and get_min on an empty stack raise IndexError.

Example

s = MinStack()
s.push(5); s.push(2); s.push(7); s.push(2); s.push(-1)
s.get_min()  -> -1
s.pop()      -> -1
s.get_min()  -> 2
s.pop()      -> 2
s.get_min()  -> 2      # the other 2 is still there
s.pop()      -> 7
s.pop()      -> 2
s.get_min()  -> 5
s.top()      -> 5

Constraints

• Up to 10^5 operations; values are any integers, including negatives and duplicates.
• Every operation O(1) worst case (not amortized).

Clarifying questions

• What should operations on an empty stack do: raise, or return None?
• Can values repeat, and can they be negative?
• Is O(n) extra memory acceptable, or should the extra memory be as small as possible?
• Should get_max be supported too?

What a strong answer covers

• A second stack holding the minimum at each depth: push min(x, current_min) with every push, pop both together. Simple and clearly correct.
• The memory-saving variant: push onto the min stack only when x <= current_min and pop from it only when the popped value equals its top. The <= (not <) is what keeps duplicates of the minimum correct.
• Alternatives: pairs (value, min_so_far) on one stack, or storing differences from the minimum to use O(1) extra memory (and the overflow risk in languages with fixed-width integers).
• Edge cases: empty stack, a single element, repeated minimums, negative numbers.
• Tests against a plain list that computes min each time.

Follow-ups

• Add get_max as well.
• Build a queue with O(1) get_min (two min stacks, or a monotonic deque).
• Support pop_min(): remove the minimum wherever it is. What does it cost now?
• Make it safe for several threads.