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 stack), I also push it onto the minimum stack. When popping, if the value removed from the main stack equals the top of the minimum stack, I pop from the minimum stack as well. This ensures that the minimum function simply returns the top of the minimum stack in O(1) time.
Common Mistakes to Avoid
- Forgetting to update the minimum stack on duplicates
- Assuming a single variable is sufficient
- Incorrectly handling empty stack states
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you implement a queue using two stacks?
Medium
Goldman SachsFind K Closest Elements (Heaps)
Medium
MetaConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDesign a Set with $O(1)$ `insert`, `remove`, and `check`
Easy
CiscoWhy are you suitable for this specific role at Amazon?
Medium
AmazonDesign a 'Trusted Buyer' Reputation Score for E-commerce
Medium
Amazon