How do you implement a stack with push pop and min operations in constant time?
Direct Answer
This classic problem tests your ability to design a data structure that supports minimum retrieval efficiently alongside standard stack operations. It focuses on space-time trade-offs.
Why Interviewers Ask This
Amazon asks this to verify deep understanding of stack internals and auxiliary data structures. They want to see if you can achieve O(1) for all operations, including getMin(), which is non-trivial. This reveals your ability to think about caching state or using secondary stacks to track history. It is a fundamental test of algorithmic design patterns.
How to Answer This Question
Explain the need for a secondary stack to track the minimums. When pushing, if the new value is smaller than or equal to the current minimum, push it onto the secondary stack as well. When popping, if the popped value matches the top of the secondary stack, pop from there too. Alternatively, store pairs of (value, current_min) in a single stack. Detail the logic for each operation and confirm that both push and pop remain O(1).
Key Points to Cover
- Use two stacks for values and minimums
- Push to min-stack only when new min found
- Pop from min-stack on matching removal
- Ensure O(1) for all operations
Sample Answer
I would implement this using two stacks: one for the actual values and another for tracking the minimums. When pushing a value, I add it to the main stack. If the value is less than or equal to the current minimum (top o…
Common Mistakes to Avoid
- Trying to scan the whole stack for minimum
- Forgetting to update the min-stack on push
- Incorrectly popping from the min-stack
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.