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.
1#include <stdio.h>
2#include <limits.h>
3#define MAX_SIZE 30000
4
5typedef struct {
6
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.
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.
1class MinStack:
2 def __init__
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.
Python takes advantage of tuples to store both the value and current minimum together. When popping or retrieving the top, the value is easily accessible, and minimum retrieval likewise by referring to the second element of the tuple.