How can you implement a stack with push, pop, and min operations in constant time?
This classic problem tests the ability to design data structures that support multiple operations efficiently. It often involves using auxiliary storage to track minimums.
Why Interviewers Ask This
Implementing O(1) min operations challenges candidates to think beyond standard stack implementations. It evaluates creativity in space-time trade-offs and understanding of stack mechanics.
How to Answer This Question
Propose using a second stack to store the minimum values alongside the main stack. When pushing, compare with the current minimum and push the smaller value to the min-stack. When popping, pop from both stacks simultaneously. Alternatively, store differences to save space.
Key Points to Cover
- Use auxiliary stack for minimums
- Push logic depends on current min
- Pop from both stacks if needed
- Ensure O(1) for all operations
Sample Answer
I can use two stacks: one for actual values and one for tracking minimums. When pushing a new value, I push it onto the main stack. If it is smaller than or equal to the current minimum, I also push it onto the min-stack. When popping, if the popped value equals the top of the min-stack, I pop from there too. This ensures min() is always O(1).
Common Mistakes to Avoid
- Scanning the stack for min every time
- Forgetting to update min-stack on push
- Incorrect pop logic for duplicates
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