Min Stack
MedPrompt
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.
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 - 1- Methods
pop,topandgetMinoperations will always be called on non-empty stacks. - At most
3 * 104calls will be made topush,pop,top, andgetMin.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a single stack, but instead of storing just the integer values, it stores a pair of integers for each entry. Each pair consists of the value itself and the minimum value in the stack at the time of the push operation. This ensures that the minimum element is always available at the top of the stack, along with the actual top element.
Algorithm
- Data Structure: Use a single stack where each element is a pair
(value, current_minimum). push(val):- If the stack is empty, the new minimum is
valitself. - Otherwise, the new minimum is the smaller value between
valand the minimum of the element currently at the top of the stack. - Push a new pair
(val, new_minimum)onto the stack.
- If the stack is empty, the new minimum is
pop():- Simply pop the top pair from the stack.
top():- Peek at the top pair and return its
valuecomponent.
- Peek at the top pair and return its
getMin():- Peek at the top pair and return its
current_minimumcomponent.
- Peek at the top pair and return its
Walkthrough
To implement this, we can create a helper class or a record to store the pair (value, min). When we push a new element val, we look at the minimum of the current top element. The new minimum to be stored with val will be Math.min(val, stack.peek().min). If the stack is empty, the minimum is just val. This way, the min part of the top pair always holds the minimum value of the entire stack. The getMin() operation becomes trivial: just peek at the top element and return its stored minimum. pop() and top() also remain simple, operating on the pairs.
class MinStack { // Inner class to store the value and the minimum at that point private class Node { int val; int min; Node(int val, int min) { this.val = val; this.min = min; } } private Stack<Node> stack; public MinStack() { stack = new Stack<>(); } public void push(int val) { int currentMin; if (stack.isEmpty()) { currentMin = val; } else { // The new minimum is the minimum of the new value and the previous minimum currentMin = Math.min(val, stack.peek().min); } stack.push(new Node(val, currentMin)); } public void pop() { stack.pop(); } public int top() { return stack.peek().val; } public int getMin() { return stack.peek().min; }}Complexity
Time
O(1)
Space
O(N)
Trade-offs
Pros
Conceptually straightforward.
All operations are guaranteed O(1) time.
Encapsulates all required information within a single data structure.
Cons
Uses significantly more space than other O(1) time solutions, as it stores a minimum value for every single element pushed onto the stack.
A classic and highly intuitive solution involves using two stacks. One stack, the main stack, behaves like a normal stack and holds all the elements. The second stack, the "min stack," is used exclusively to keep track of the current minimum element. The top of the min stack is always the minimum element in the main stack.
Algorithm
- Data Structures: Use a primary stack (
stack) for all elements and a secondary stack (minStack) to track minimums. push(val):- Always push
valonto thestack. - If
minStackis empty orvalis less than or equal to the value at the top ofminStack, pushvalontominStackas well.
- Always push
pop():- Pop the top element from
stack. - If the popped value is equal to the top of
minStack, pop fromminStacktoo.
- Pop the top element from
top():- Return the top of
stack.
- Return the top of
getMin():- Return the top of
minStack.
- Return the top of
Walkthrough
When we push a new element val, it always goes into the main stack. We then compare val with the element at the top of the minStack. If val is less than or equal to the current minimum, it represents a new minimum (or an equally small value), so we push it onto the minStack. The "equal to" condition is crucial for handling cases with duplicate minimum values. When we pop an element, we check if the popped element is the same as the one at the top of the minStack. If it is, we must also pop from the minStack to expose the next-smallest minimum. This ensures that getMin() can always return the correct minimum in O(1) time by simply peeking at the minStack.
import java.util.Stack; class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { stack.push(val); // Push to minStack only if it's a new minimum or equal to the current minimum if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } } public void pop() { int popped = stack.pop(); // If the popped element was the minimum, remove it from minStack as well if (popped == minStack.peek()) { minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); }}Complexity
Time
O(1)
Space
O(N)
Trade-offs
Pros
Achieves O(1) time complexity for all operations.
More space-efficient on average than the pair approach, as the min stack only grows when a new, smaller element is added.
Cons
Requires managing two separate data structures.
In the worst-case scenario (pushing elements in a strictly decreasing order), the space complexity is O(N), same as the less efficient pair approach.
This is the most space-optimized approach that maintains O(1) time complexity for all operations. It uses only a single stack and one extra variable to keep track of the minimum. Instead of storing the actual values on the stack, we store the difference (or "gap") between the pushed value and the current minimum value. This encoding allows us to deduce the actual value and restore previous minimums during pop operations.
Algorithm
- Data Structures: Use a single
Stack<Long>and along minvariable. push(val):- If the stack is empty, push
0Land setmin = val. - Otherwise, calculate the difference
diff = (long)val - min. Pushdiffonto the stack. - If
val < min, updatemin = val.
- If the stack is empty, push
pop():- Pop
difffrom the stack. - If
diff < 0, it means the minimum element was just popped. Restore the previous minimum by updatingmin = min - diff.
- Pop
top():- Peek at
difffrom the stack. - If
diff < 0, the actual top value is the currentmin. - Otherwise, the actual top value is
min + diff.
- Peek at
getMin():- Return the current value of the
minvariable.
- Return the current value of the
Walkthrough
We maintain a variable min that holds the current minimum value in the stack. The stack itself will store long values to avoid overflow since the difference between two int values can exceed the int range.
When pushing a value val, we push the difference (long)val - min onto the stack. If val is smaller than the current min, we update min to val.
When popping, if the popped difference is negative, it signifies that the element being removed was a minimum. The value of min before this element was pushed can be recovered using the formula previous_min = current_min - diff. We update min to this restored value. If the difference is non-negative, the min value is unaffected.
The top operation similarly uses the difference at the top of the stack to calculate the actual top value relative to the current min.
import java.util.Stack; class MinStack { private Stack<Long> stack; private long min; public MinStack() { stack = new Stack<>(); } public void push(int val) { if (stack.isEmpty()) { stack.push(0L); min = val; } else { long diff = (long)val - min; stack.push(diff); if (diff < 0) { // New value is the new min min = val; } } } public void pop() { long diff = stack.pop(); if (diff < 0) { // The popped element was a minimum. Restore the previous minimum. // previous_min = current_min - diff min = min - diff; } } public int top() { long diff = stack.peek(); if (diff < 0) { // The top element is the current minimum return (int)min; } else { // Reconstruct the original value: val = min + diff return (int)(min + diff); } } public int getMin() { return (int)min; }}Complexity
Time
O(1)
Space
O(N)
Trade-offs
Pros
Extremely space-efficient, using O(1) extra space besides the stack itself.
All operations are O(1) time complexity.
Cons
The logic is significantly more complex and less intuitive than other approaches.
Requires careful handling of data types (using
long) to prevent integer overflow when calculating differences.
Solutions
Solution
public class MinStack { private Stack < int > stk1 = new Stack < int >(); private Stack < int > stk2 = new Stack < int >(); public MinStack () { stk2 . Push ( int . MaxValue ); } public void Push ( int x ) { stk1 . Push ( x ); stk2 . Push ( Math . Min ( x , GetMin ())); } public void Pop () { stk1 . Pop (); stk2 . Pop (); } public int Top () { return stk1 . Peek (); } public int GetMin () { return stk2 . Peek (); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.Push(x); * obj.Pop(); * int param_3 = obj.Top(); * int param_4 = obj.GetMin(); */class MinStack { private Deque < Integer > stk1 = new ArrayDeque <>(); private Deque < Integer > stk2 = new ArrayDeque <>(); public MinStack () { stk2 . push ( Integer . MAX_VALUE ); } public void push ( int val ) { stk1 . push ( val ); stk2 . push ( Math . min ( val , stk2 . peek ())); } public void pop () { stk1 . pop (); stk2 . pop (); } public int top () { return stk1 . peek (); } public int getMin () { return stk2 . peek (); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */var MinStack = function () { this . stk1 = []; this . stk2 = [ Infinity ]; }; /** * @param {number} val * @return {void} */ MinStack . prototype . push = function ( val ) { this . stk1 . push ( val ); this . stk2 . push ( Math . min ( this . stk2 [ this . stk2 . length - 1 ], val )); }; /** * @return {void} */ MinStack . prototype . pop = function () { this . stk1 . pop (); this . stk2 . pop (); }; /** * @return {number} */ MinStack . prototype . top = function () { return this . stk1 [ this . stk1 . length - 1 ]; }; /** * @return {number} */ MinStack . prototype . getMin = function () { return this . stk2 [ this . stk2 . length - 1 ]; }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(val) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.getMin() */class MinStack { public: MinStack () { stk2 . push ( INT_MAX ); } void push ( int val ) { stk1 . push ( val ); stk2 . push ( min ( val , stk2 . top ())); } void pop () { stk1 . pop (); stk2 . pop (); } int top () { return stk1 . top (); } int getMin () { return stk2 . top (); } private: stack < int > stk1 ; stack < int > stk2 ; }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */class MinStack : def __init__ ( self ): self . sk = [] self . minsk = [ inf ] # trick, avoid later empty-check for min-stack def push ( self , x : int ) -> None : self . sk . append ( x ) self . minsk . append ( min ( x , self . minsk [ - 1 ])) def pop ( self ) -> None : if not self . sk : return self . sk . pop () self . minsk . pop () def top ( self ) -> int : return self . sk [ - 1 ] def getMin ( self ) -> int : return self . minsk [ - 1 ] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin() ############ class MinStack : def __init__ ( self ): self . sk = [] self . minsk = [] def push ( self , val : int ) -> None : self . sk . append ( val ) # empty check self . minsk . append ( val if not self . minsk else min ( val , self . minsk [ - 1 ])) def pop ( self ) -> None : if not self . sk : return self . sk . pop () self . minsk . pop () def top ( self ) -> int : return self . sk [ - 1 ] def getMin ( self ) -> int : return self . minsk [ - 1 ] # optimize above, using only 1 stack, with stack element as tuple: (val, its associated min) class MinStack : def __init__ ( self ): self . _stack = [] def push ( self , x : int ) -> None : cur_min = self . getMin () if x < cur_min : cur_min = x self . _stack . append (( x , cur_min )) def pop ( self ) -> None : self . _stack . pop () def top ( self ) -> int : if not self . _stack : return None else : return self . _stack [ - 1 ][ 0 ] def getMin ( self ) -> int : if not self . _stack : return float ( 'inf' ) else : return self . _stack [ - 1 ][ 1 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.