Design a stack that returns its minimum element in O(1).

How to think about it

Recognise the pattern

When a data structure problem asks for O(1) access to some aggregate (min, max, median) that would normally require scanning, think about maintaining that aggregate incrementally — update it on every push/pop so it is always ready.

This is the same idea behind a running maximum in a sliding window, or a monotonic deque.

Build the approach step by step

Naive approach: store elements in a list, scan for the minimum on each get_min() call. O(n) per query — fails the requirement.

The insight: at any point in time, the minimum is determined by what is currently in the stack. When you push a new element, the new minimum is min(new_element, current_min). When you pop, the previous minimum is restored. A second stack that records the minimum at each level tracks all of this automatically.

Parallel min-stack:

• push(x): push x to main stack; push min(x, min_stack[-1]) to min stack.
• pop(): pop both stacks together.
• get_min(): return min_stack[-1].

push 5:  main=[5]     min=[5]
push 3:  main=[5,3]   min=[5,3]
push 7:  main=[5,3,7] min=[5,3,3]  <- 3 is still min
pop:     main=[5,3]   min=[5,3]    <- 3 correctly restored
get_min: -> 3

Complexity

Operation	Time	Space
push	O(1)	—
pop	O(1)	—
top	O(1)	—
get_min	O(1)	—
Overall space	—	O(n)

The space doubles compared to a plain stack, but every operation is constant time.