How do you implement a stack with push pop and min operations in constant time?
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 of the min-stack), I also push it onto the min-stack. When popping, if the value being removed equals the top of the min-stack, I pop from the min-stack as well. This ensures the top of the min-stack always holds the current minimum. Both push and pop operations take constant time, and retrieving the minimum is simply accessing the top of the second stack.
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
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 add two numbers represented by linked lists?
Medium
AmazonWrite Selenium and Java code to automate an Amazon search
Medium
InfosysHow do you implement binary search on a sorted array?
Easy
MicrosoftWhat is the difference between value type and reference type?
Easy
TCSWhy are you suitable for this specific role at Amazon?
Medium
AmazonDesign a 'Trusted Buyer' Reputation Score for E-commerce
Medium
Amazon