Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.
For example:
push(5) -> stack: [5], min: 5 push(3) -> stack: [5, 3], min: 3 push(7) -> stack: [5, 3, 7], min: 3 getMin() -> returns 3 pop() -> removes 7, min is still 3 pop() -> removes 3, min is now 5
The challenge is maintaining O(1) getMin even after elements are popped. How would you track the minimum efficiently?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
A single variable tracking the current minimum breaks when that minimum is popped. You need to know what the previous minimum was.
- Hint 2
Consider maintaining a second stack that tracks the minimum at each level of the main stack.
- Hint 3
Each time you push, also push onto the min stack the smaller of the new value and the current minimum. Pop from both stacks together.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.