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.
This approach utilizes two stacks. One stack will hold the main elements, while the other stack will keep track of the minimum elements. When you push a value, it's added to the main stack, and if it's less than or equal to the current minimum, it's also pushed onto the min stack. During a pop operation, if the value being popped is the current minimum, it's also popped from the min stack.
The C solution uses simple arrays to maintain the main stack and the minimum stack. We use indices to track the current position in both stacks. The main operations are very similar to basic stack operations but with an additional stack handling minimums.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.
This approach reduces space usage by storing a pair (value, minimum so far) in a single stack. Each element maintains the current minimum alongside its actual value, providing quick minimum retrieval by just examining the top of the stack.
In C++, the standard stack is used, but each element is stored as a pair. The pair consists of the value and the minimum value at that time. This ensures that when popping, the integrity of the minimum remains intact because each element 'remembers' what the minimum was.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), each element only holds a pair so space is efficient relative to the number of elements.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Using two stacks | Time Complexity: O(1) for each operation. |
| Using a single stack with tuple pairs | Time Complexity: O(1) for each operation. |
| Default Approach | — |
| 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. |
Design Min Stack - Amazon Interview Question - Leetcode 155 - Python • NeetCode • 330,981 views views
Watch 9 more video solutions →Practice Min Stack with our built-in code editor and test cases.
Practice on FleetCode