How do you implement a stack with push, pop, and min operations in O(1)?
This classic problem requires designing a stack data structure where retrieving the minimum element takes constant time alongside standard stack operations.
Why Interviewers Ask This
This question tests deep understanding of auxiliary data structures and space-time trade-offs. Interviewers want to see if you can maintain state efficiently without re-scanning the stack. It demonstrates your ability to engineer solutions that meet strict performance constraints typical in high-frequency trading or real-time systems.
How to Answer This Question
Explain the naive approach of scanning the stack for min, noting its O(N) cost. Propose using an auxiliary stack to store the minimums. Describe the logic: push to main stack, and push to min-stack only if the new element is smaller than or equal to the current min. For pop, pop from both stacks if the popped element matches the current min. Analyze space complexity O(N) and time complexity O(1) for all operations.
Key Points to Cover
- Use an auxiliary stack to track minimums
- Push to min-stack only when necessary
- Maintain synchronization between main and min stacks
- Ensure O(1) time for all three operations
Sample Answer
To achieve O(1) for min, I will use two stacks: one for storing all elements and another specifically for tracking minimums. When pushing an element, I add it to the main stack. If the new element is less than or equal t…
Common Mistakes to Avoid
- Storing all elements in the min-stack unnecessarily
- Forgetting to update min-stack on equal values
- Not handling empty stack scenarios properly
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.