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.The goal of #155 Min Stack is to design a stack that, besides the usual push, pop, and top operations, can also return the minimum element in constant time using getMin(). A naive solution would scan the entire stack to find the minimum, but that would take O(n) time per query, which is inefficient.
The key idea is to maintain additional information while pushing elements. One common approach is to use an auxiliary structure that keeps track of the current minimum at each step. This can be done with a second stack storing minimum values or by storing pairs like (value, currentMin) in a single stack.
Whenever a new element is pushed, the current minimum is updated and stored alongside it. When elements are popped, the minimum automatically rolls back to the previous value. This design ensures that all operations—push, pop, top, and getMin—run in O(1) time while using additional O(n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack with auxiliary min stack | O(1) for push, pop, top, getMin | O(n) |
| Single stack storing (value, currentMin) | O(1) for all operations | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Consider each node in the stack having a minimum value. (Credits to @aakarshmadhavan)
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.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.
1class MinStack:
2 def __init__(self):
3 self.stack = []
4 self.min_stack = []
5
6 def push(self, val: int) -> None:
7 self.stack.append(val)
8 if not self.min_stack or val <= self.min_stack[-1]:
9 self.min_stack.append(val)
10
11 def pop(self) -> None:
12 if self.stack.pop() == self.min_stack[-1]:
13 self.min_stack.pop()
14
15 def top(self) -> int:
16 return self.stack[-1]
17
18 def getMin(self) -> int:
19 return self.min_stack[-1]
20The Python implementation uses two lists (stacks). The main stack operates as a typical stack, while the min_stack keeps track of the current minimums. Push and pop operations involve conditionally modifying min_stack based on whether the pushed or popped values affect the current minimum.
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.
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.
1#include <stack>
2#include <climits>
3class MinStack {
4 std::stack<std::pair<int, int>> stack;
public:
MinStack() {}
void push(int val) {
if (stack.empty())
stack.emplace(val, val);
else
stack.emplace(val, std::min(val, stack.top().second));
}
void pop() {
stack.pop();
}
int top() {
return stack.top().first;
}
int getMin() {
return stack.top().second;
}
};
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Min Stack is a common interview question because it tests understanding of stacks, auxiliary data structures, and constant-time design constraints. Variants of this problem frequently appear in coding interviews at top tech companies.
The optimal approach keeps track of the minimum element while pushing values onto the stack. This is typically done using an auxiliary stack that stores the current minimum or by storing pairs of (value, minSoFar). Both approaches allow getMin() to run in O(1) time.
Scanning the stack each time getMin() is called would take O(n) time. Since the problem requires constant-time operations, we must store minimum information during push operations to avoid repeated traversal.
A stack combined with an additional structure to track minimum values works best. Many implementations use two stacks or a single stack storing pairs of values and the current minimum. This ensures constant-time operations.
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.