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.

Example 1:

Input: push(-7); push(4); push(-11); get_min(); pop(); top(); get_min(); push(8); get_min()
Output: [null, null, null, -11, null, 4, -7, null, -7]
Explanation: after -11 is popped the minimum reverts to -7, and pushing the larger value 8 leaves it unchanged.

Constraints:

• -10^4 <= val <= 10^4
• pop, top, and get_min are always called on a non-empty stack.
• At most 10^4 calls will be made to push, pop, top, and get_min.

Solution Breakdown

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 -7, 4, -11: min_stack becomes [-7, -7, -11]. get_min is -11. After one pop, both stacks drop their top, min_stack is [-7, -7], and get_min is -7. Pushing 8 appends min(8, -7) = -7, so the minimum stays -7.

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.