Min Stack

Problem

Observability dashboards track running metrics - the minimum latency seen so far, the lowest price in a session, the least busy server. You need a stack that supports the standard push, pop, and top operations but also exposes the current minimum in O(1), even as elements are added and removed in LIFO order.

push(-2), push(0), push(-3) → get_min() returns -3
pop()                        → top() returns 0, get_min() returns -2
push(5)                      → get_min() returns -2

Solution

Approach: Parallel auxiliary stack tracking the running minimum.

Keep two stacks that always grow and shrink together: stack holds the values, and min_stack holds, at each level, the minimum of everything in stack up to and including that level. On push, append the value to stack, then append min(val, min_stack[-1]) to min_stack - or just val when min_stack is empty, since the first element is its own minimum. On pop, remove the top of both stacks so they stay the same height. top returns stack[-1]; get_min returns min_stack[-1] directly, which is O(1).

The key insight is that a single min variable cannot recover the previous minimum once the current minimum is popped. By recording the running minimum at every level, min_stack[-1] always answers "what is the smallest value still present," and popping it cleanly exposes the minimum of the shorter stack underneath - no rescan needed. Trace pushing -2, 0, -3: min_stack becomes [-2, -2, -3]. get_min is -3. After one pop, both stacks drop their top, min_stack is [-2, -2], and get_min is -2. Pushing 5 appends min(5, -2) = -2, so the minimum stays -2.

Edge cases: Pushing a value larger than the current minimum duplicates that minimum on min_stack, which is what keeps pop O(1) instead of forcing a search. get_min on an empty stack would raise IndexError; the problem guarantees it is never called empty.

Complexity: O(1) time for every operation - all are stack pushes, pops, or top reads. O(n) space for the auxiliary stack, one entry per element.