MediumStacks QueuesAI interview only
Min Stack
Asked atamazongooglemicrosoftbloombergappleuber
01 · Problem
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack()initializes the stack object.void push(int val)pushes the elementvalonto the stack.void pop()removes the element on the top of the stack.int top()gets the top element of the stack.int getMin()retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
02 · Examples
Example 01
Input
["MinStack","push","push","push","getMin","pop","top","getMin"], [[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
After pushing -2, 0, -3: getMin returns -3. After popping -3: top returns 0 and getMin returns -2.
Example 02
Input
["MinStack","push","push","getMin","pop","getMin"], [[],[1],[0],[],[],[]]
Output
[null,null,null,0,null,1]
After pushing 1 and 0: getMin returns 0. After popping 0: getMin returns 1.
Example 03
Input
["MinStack","push","push","push","getMin","pop","getMin","pop","getMin"], [[],[2],[1],[3],[],[],[],[],[]]
Output
[null,null,null,null,1,null,1,null,2]
After pushing 2, 1, 3: getMin returns 1. After popping 3: getMin still returns 1. After popping 1: getMin returns 2.
03 · Constraints
- 01-231 <= val <= 231 - 1
- 02Methods pop, top and getMin operations will always be called on non-empty stacks.
- 03At most 3 * 104 calls will be made to push, pop, top, and getMin.
04 · Optimal complexity
- Time
- O(1)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.