Watch 10 video solutions for Min Stack, a medium level problem involving Stack, Design. This walkthrough by NeetCode has 255,349 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 element val onto 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.
Example 1:
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Constraints:
-231 <= val <= 231 - 1pop, top and getMin operations will always be called on non-empty stacks.3 * 104 calls will be made to push, pop, top, and getMin.Problem Overview: Design a stack that supports the standard operations push, pop, and top, while also returning the minimum element with getMin() in constant time. The challenge is maintaining the minimum value without scanning the entire stack each time.
Approach 1: Two Stacks (O(1) time, O(n) space)
This approach keeps two stacks: the main stack storing all elements and a second stack tracking the current minimum. When you push a value, compare it with the current minimum. If it is smaller or equal, also push it onto the min stack. During pop, remove the value from the main stack and check whether it matches the top of the min stack; if so, pop from the min stack as well. The key insight is that the second stack stores only the values that become the new minimum at some point. This guarantees that getMin() simply returns the top of the min stack in O(1) time while keeping overall space at O(n).
Approach 2: Single Stack with Tuple Pairs (O(1) time, O(n) space)
Instead of maintaining two separate structures, each stack entry stores a pair: (value, currentMin). When pushing a new element, compute the minimum between the new value and the previous minimum stored at the top of the stack. Store that result alongside the value. Now every stack node already knows the minimum up to that point. On pop, simply remove the top pair. top() returns the value component, and getMin() returns the stored minimum component. This design keeps all operations in constant time and often results in cleaner implementations because the minimum state travels with each element.
Both solutions rely on the core idea that the minimum value must be updated incrementally during push operations rather than recomputed later. Without this trick, getMin() would require iterating through the entire stack, resulting in O(n) time.
This problem is a classic example of augmenting a data structure with additional metadata. Interviewers often use it to evaluate your understanding of stack behavior and your ability to extend a structure for constant-time queries. It also appears in discussions around system and data structure design, where tracking auxiliary state efficiently is common.
Recommended for interviews: The two-stack solution is the most widely expected answer because it clearly demonstrates the idea of maintaining a secondary structure for minimum tracking. The tuple-pair approach is equally optimal and sometimes preferred in languages where storing pairs or objects is straightforward. Showing the reasoning from naive O(n) minimum lookup to an O(1) design signals strong problem-solving ability.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Stacks | O(1) for push, pop, top, getMin | O(n) | Most common interview solution. Easy to reason about and clearly separates value storage from minimum tracking. |
| Single Stack with Tuple Pairs | O(1) for all operations | O(n) | Cleaner implementation when storing pairs is convenient. Keeps value and current minimum together in the same structure. |