FAANGPrep Sprint
Min Stack
Design a stack that supports retrieving the minimum element in constant time.
Problem Understanding
Design a stack that supports push, pop, top, and getMin operations, all in O(1) time.
push(val): Pushes element val onto stack.pop(): Removes element on top of stack.top(): Gets the top element.getMin(): Retrieves minimum element in the stack.
Algorithm Strategy
A standard stack gives O(1) push/pop, but finding the minimum usually takes O(N). To get O(1) min, we trade Space for Time.
Strategy:
Maintain a second stack, minStack. Whenever we push a value x onto the mainStack, we also push min(x, minStack.top()) onto the minStack. The top of minStack always represents the minimum of the mainStack at that height.
Interactive Visualization
EVERY OPERATION O(1)
EMPTY
operations
stack
empty
minStack
empty
Size
0
Min
—
returned
Nothing read yet
Two empty stacks: stack holds the values, minStack the minimum at each height
Next
push 2: add it to stack
Ops
Visualize two stacks growing in parallel. The MinStack tracks the minimum value seen 'so far'.