Min Stack — Problem Statement & Solution Guide
Problem Description
Design a data structure that extends the standard stack interface with an additional capability to retrieve the current minimum value in constant time. The structure must support four primary operations: pushing an integer onto the top, removing the top element, retrieving the top element without removal, and querying the smallest integer currently present in the stack.
Implement a class named MinStack that initializes an empty stack. The class must provide the following methods: push(val) to add an integer val to the top of the stack; pop() to remove the top element; top() to return the top element; and getMin() to return the minimum element among all elements currently in the stack. All operations must execute in O(1) time complexity.
The implementation must handle edge cases such as an empty stack for pop, top, and getMin operations, though the problem guarantees that these operations will only be called when the stack is non-empty. The solution should maintain the integrity of the stack order while efficiently tracking the minimum value without scanning the entire structure upon each query.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Min Stack"
WHY DOES IT MATTER?
This pattern demonstrates the 'Auxiliary Stack' or 'Shadow Stack' technique, where a secondary data structure mirrors the primary one to store derived state. It is essential for problems requiring constant-time access to aggregate statistics (min, max, sum, average) that change dynamically with insertions and deletions.
OPTIMIZATION CHALLENGE
The key insight is that you don't need to store the minimum for every single element, but you do need to know what the minimum was *before* the current element was pushed. By pushing the current minimum onto an auxiliary stack only when a new minimum is found (or pushing the current min every time for simpler implementation), you preserve the history of minimums.
REAL-WORLD CONNECTION
Think of a stock trading terminal. You need to see the current lowest bid price instantly. If you had to recalculate the lowest bid from all active orders every time a new order came in or an order was canceled, the UI would lag. The Min Stack is like maintaining a 'current lowest bid' variable that updates only when necessary, ensuring instant display.
In interviews, clarify if getMin() must be O(1). If yes, propose the auxiliary stack. If space is a concern, mention the optimization of only pushing to the auxiliary stack when a new minimum is encountered, which reduces space usage in cases where the input is not strictly decreasing.
COMPLEXITY AT A GLANCE
O(1)O(n)Core Theory — Why This Approach?
The Min Stack problem is a classic example of trading space for time to achieve constant-time complexity for non-trivial queries. A naive approach would involve scanning the entire stack to find the minimum element during every getMin() call, resulting in O(n) time complexity per query. This becomes prohibitively expensive in high-frequency trading systems or real-time monitoring dashboards where latency must be minimized, even if the stack size is moderate. The fundamental challenge is that removing the current minimum element (via pop()) can reveal a new minimum that was previously hidden, making it impossible to simply store a single global minimum variable.
Interview Questions on This Problem
Q1At a fintech platform, we need to track the lowest price of a stock in the last N transactions. How would you adapt the Min Stack to handle a sliding window of size N instead of a full stack?
You would use a deque (double-ended queue) to maintain the sliding window and a monotonic queue (or a specialized min-heap with lazy deletion) to track the minimum. Alternatively, if the window is fixed and operations are strictly append/remove-from-front, a monotonic deque that stores indices can provide O(1) amortized time for min queries by maintaining elements in increasing order.
Q2In a distributed system, multiple nodes push to a shared logical stack. How would you ensure `getMin()` remains consistent if the stack is sharded across nodes?
This requires a coordination layer. One approach is to use a centralized coordinator that aggregates the minimums from each shard. Each shard maintains its own local Min Stack. The global getMin() becomes a reduction operation (taking the min of all local mins). This introduces network latency, so caching the global min with a TTL or using a consensus protocol like Raft for the min-state is necessary for strong consistency.
Q3If memory is extremely constrained, can you implement Min Stack with O(1) space overhead per element instead of O(n) total space?
Strictly O(1) space overhead per element is not possible for arbitrary sequences if you require O(1) getMin() time, because you must store the historical minimums to recover from pops. However, if the input sequence has specific properties (e.g., monotonic), you could optimize. In general, the O(n) space overhead is the theoretical lower bound for this specific constraint set.
Examples
Input
MinStack obj = new MinStack(); obj.push(15); obj.push(3); obj.push(7); obj.getMin(); obj.pop(); obj.getMin(); obj.top();
Output
null null null null 3 null 3 null 7
Explanation: 1. Initialize an empty stack. 2. Push 15: Stack is [15], Min is 15. 3. Push 3: Stack is [15, 3], Min is 3. 4. Push 7: Stack is [15, 3, 7], Min is 3. 5. getMin(): Returns 3. 6. pop(): Removes 7. Stack is [15, 3], Min is 3. 7. getMin(): Returns 3. 8. top(): Returns 3.
Input
MinStack obj = new MinStack(); obj.push(100); obj.push(200); obj.push(50); obj.getMin(); obj.pop(); obj.getMin(); obj.pop(); obj.getMin();
Output
null null null null 50 null 50 null 100
Explanation: 1. Initialize an empty stack. 2. Push 100: Stack is [100], Min is 100. 3. Push 200: Stack is [100, 200], Min is 100. 4. Push 50: Stack is [100, 200, 50], Min is 50. 5. getMin(): Returns 50. 6. pop(): Removes 50. Stack is [100, 200], Min is 100. 7. getMin(): Returns 100. 8. pop(): Removes 200. Stack is [100], Min is 100. 9. getMin(): Returns 100.
Input
MinStack obj = new MinStack(); obj.push(-5); obj.push(-10); obj.push(-2); obj.getMin(); obj.pop(); obj.getMin(); obj.top();
Output
null null null null -10 null -10 null -10
Explanation: 1. Initialize an empty stack. 2. Push -5: Stack is [-5], Min is -5. 3. Push -10: Stack is [-5, -10], Min is -10. 4. Push -2: Stack is [-5, -10, -2], Min is -10. 5. getMin(): Returns -10. 6. pop(): Removes -2. Stack is [-5, -10], Min is -10. 7. getMin(): Returns -10. 8. top(): Returns -10.
Constraints
- -2^31 <= val <= 2^31 - 1
- At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
- pop, top, and getMin will only be called when the stack is not empty.
- The stack size will not exceed 10^5 at any point.
Optimal Approach & Strategy
Maintain a second auxiliary stack that tracks the minimum value at each level of the main stack. Push the current minimum onto the auxiliary stack whenever a new element is added, ensuring O(1) access to the current minimum.
Brute Force Approach
Store all elements in a standard stack. For getMin(), iterate through the entire stack to find the minimum value, which takes O(n) time per query.
Verified Code Solutions
class MinStack { constructor() { this.stack = []; this.minStack = []; } push(x) { this.stack.push(x); if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) { this.minStack.push(x); } } pop() { if (this.stack.length > 0) { if (this.stack[this.stack.length - 1] === this.minStack[this.minStack.length - 1]) { this.minStack.pop(); } this.stack.pop(); } } top() { return this.stack[this.stack.length - 1]; } getMin() { return this.minStack[this.minStack.length - 1]; } }class MinStack { private: std::stack<int> stack; std::stack<int> minStack; public: void push(int x) { stack.push(x); if (minStack.empty() || x <= minStack.top()) { minStack.push(x); } } void pop() { if (!stack.empty()) { if (stack.top() == minStack.top()) { minStack.pop(); } stack.pop(); } } int top() { return stack.top(); } int getMin() { return minStack.top(); } };class MinStack { private java.util.Stack<Integer> stack; private java.util.Stack<Integer> minStack; public MinStack() { stack = new java.util.Stack<>(); minStack = new java.util.Stack<>(); } public void push(int x) { stack.push(x); if (minStack.isEmpty() || x <= minStack.peek()) { minStack.push(x); } } public void pop() { if (!stack.isEmpty()) { if (stack.peek().equals(minStack.peek())) { minStack.pop(); } stack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }class MinStack: def __init__(self): self.stack = []; self.minStack = []; def push(self, x): self.stack.append(x); if not self.minStack or x <= self.minStack[-1]: self.minStack.append(x); def pop(self): if self.stack: if self.stack[-1] == self.minStack[-1]: self.minStack.pop(); self.stack.pop(); def top(self): return self.stack[-1]; def getMin(self): return self.minStack[-1];class MinStack { constructor() { this.stack = []; this.minStack = []; } push(x) { this.stack.push(x); if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) { this.minStack.push(x); } } pop() { if (this.stack.length > 0) { if (this.stack[this.stack.length - 1] === this.minStack[this.minStack.length - 1]) { this.minStack.pop(); } this.stack.pop(); } } top() { return this.stack[this.stack.length - 1]; } getMin() { return this.minStack[this.minStack.length - 1]; } }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.