How would you implement a stack with push, pop, and min in O(1) time?
This classic problem tests your understanding of stack operations and auxiliary data structures. It requires designing a system where retrieving the minimum element does not degrade performance.
Why Interviewers Ask This
Amazon asks this to verify deep knowledge of data structure internals. The interviewer wants to ensure you can design systems where critical operations remain constant time even under pressure. It demonstrates your ability to trade space for time efficiency, a common theme in system design.
How to Answer This Question
Explain the need for a secondary stack or variable to track the minimum. Describe pushing the current value onto the main stack and comparing it with the current minimum on the auxiliary stack. Detail how popping works by removing from both stacks if the popped value matches the minimum. Conclude by analyzing the space overhead required for the extra stack.
Key Points to Cover
- Use two stacks for values and minimums
- Push to min stack only if new value is smaller
- Pop from min stack if matching the main pop
- Maintain O(1) for all operations
Sample Answer
I would maintain two stacks: one for storing actual values and another for tracking the minimums. When pushing a value, I add it to the main stack. If it is less than or equal to the current minimum (top of the second st…
Common Mistakes to Avoid
- Forgetting to update the minimum stack on duplicates
- Assuming a single variable is sufficient
- Incorrectly handling empty stack states
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.