Design a Stack with O(1) min operation
Filed under Microsoft · Also reported at Zilingo
Free read 1 of 3Ensure all standard stack operations must be supported alongside min in O(1) time.
The question
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Constraints
- Methods push, pop, top, and getMin will be called on non-empty stacks.
- O(1) time complexity for each function.
Examples
- Input
- MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
- Output
- As described
- Why
- Maintains minimum tracking across state changes.
Approach
Ensure all standard stack operations must be supported alongside min in O(1) time.
Scan the entire stack on every getMin call, resulting in O(n) time for minimum retrieval.
Use an auxiliary stack to keep track of minimums, or store tuples of (val, current_min) in a single stack.
Pushing negative numbers, pushing identical minimum values consecutively, and operations on an empty stack.
Solution
O(1) time for all operations, O(n) space
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
Tips
- What they are testing: Test duplicate minimum values to ensure pop operations correctly handle removing one instance while keeping the prior minimum.
- Common mistake: Updating the min tracker only when a strictly smaller value is pushed, which fails when duplicate minimums are popped.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.