LeetCode 155 ·
Medium
Min Stack
Design a stack that also returns its minimum in O(1).
Try it
Step through the core mechanic. The simulator below runs the stack / monotonic stack shape this problem is built on.
Interactive · bracket matching push openers, pop on a matching closer
input
(
[
]
{
}
)
stack
empty
empty stack
The approach
Alongside the value stack, keep a min stack that pushes min(value, currentMin) on each push and pops in lockstep. The min stack top is always the running minimum.
| Aspect | Value |
|---|---|
| Pattern | Stack / monotonic stack |
| Recognise it by | O(1) push, pop, and current minimum. |
| Time complexity | O(1) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.