Min stack
Scenario
You have a stack of numbers, and you constantly need to know the smallest one. Scanning the whole stack takes too long.
How can we know the minimum instantly, even as numbers are added and removed?
Why it exists
Problem: While a standard stack provides O(1) access to the top element, querying a global property like the minimum value requires an O(n) linear scan.
Naive approach: Scanning the entire stack from top to bottom every time you need the minimum value, taking O(n) time.
Better idea: Leverage the immutable historical nature of LIFO structures. Capture a snapshot of the minimum value at the exact moment an element is pushed, storing it in a parallel auxiliary stack.
Mental model
Keep a shadow stack running next to the main stack, where every element represents the absolute minimum value seen up to that depth.
The optimal solution uses an auxiliary 'min-stack'. When pushing a value x, compare it to the current minimum (the top of the min-stack), and push the lesser of the two onto the min-stack. When popping, both stacks pop simultaneously. This guarantees the top of the min-stack always holds the global minimum of the current elements in O(1) time.
Repeated decision: When pushing x, what is smaller: x, or the current minimum at the top of the min-stack?
Explanation
Min Stack perfectly highlights how leveraging invariants can circumvent seemingly mandatory linear scans. Because the physical structure of a stack guarantees that historical elements cannot be removed out of order, the statistical properties of that history (such as the minimum) are statically locked until popped.
While the O(n) space double-stack method is completely standard, being able to articulate the O(1) mathematical differential encoding (storing a transformed value to flag a state change) demonstrates an elite understanding of state management and boundary risks (overflow).
Key points
- Invariant: The minimum state is perfectly synchronized with the main stack's lifecycle.
- Complexity: O(1) time for push, pop, and getMin.
- Gotcha: When popping, ensure the parallel minimum state is also popped to remain synchronized.
Pattern: Parallel State Tracking
Recognition cues:
- Design a stack that supports getMin/getMax in O(1)
- Need to query global state of a LIFO structure instantly
Failure signals
- Attempting to sort the stack
- Linearly scanning the stack on every getMin request
Engineering examples
Streaming min/max ('min-queue')
Reporting the minimum of a stream that supports both ends in O(1)
Two min-stacks compose into a FIFO queue that returns its minimum in amortized O(1) — the classic 'min-queue' used inside sliding-window and streaming-analytics code. The stack is the reusable building block.
Common mistakes
- Forgetting to sync pops: If you only push to the min-stack when a new minimum is found, you must be extremely careful during popping to only pop the min-stack if the popped value equals the current minimum. Using a parallel 1:1 stack avoids this sync issue entirely.
- Differential encoding underflow/overflow: An O(1) space optimization exists using mathematical differential encoding, but it risks integer overflow (`2*x - min_val`). Production systems must use 64-bit bounds checking.
Recall questions
- How does the parallel min-stack achieve O(1) time complexity for getMin()?
- Why is state snapshotting possible in a stack but harder in a dynamic array?
- What is the space complexity of the standard parallel min-stack approach?
Questions & answers
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Use a main stack for values and an auxiliary stack that pushes `min(x, current_min)`. Both pop simultaneously.
Approach: Apply the parallel synchronization mechanism.
Optimize Min Stack to use O(1) extra space.
Use differential encoding. Store an anomaly value `2*x - min_val` when a new minimum is found. Upon popping an anomaly, decode it to restore the previous minimum. Decode step: if a popped value is < current min, it was an encoded flag — recover the previous min as `2*min - popped`; the real data value equals the old min.
Approach: Mathematical state embedding.
Continue learning
Previous: Stack fundamentals
Related: Stack fundamentals