Min Stack solution and explanation
Infosys
9 more videos on this problem
Design Min Stack - Amazon Interview Question - Leetcode 155 - PythonNeetCode · 8:53 · 349K views
L4. Implement Min Stack | Stack and Queue Playlisttake U forward · 20:55 · 260K views
LeetCode 155. Min Stack (Algorithm Explained)Nick White · 8:10 · 42K views
Min Stack (LeetCode 155) | Full Solution with animations using 2 stacksNikhil Lohia · 13:19 · 16K views
Min Stack - Leetcode 155 - Stacks (Python)Greg Hogg · 8:01 · 14K views
Design Min Stack - LeetCode155 | Full Explanation with JAVA CodeJenny's Lectures CS IT · 30:39 · 10K views
LeetCode 155: Min StackEngineering Digest · 9:03 · 5K views
LEETCODE 155 (JAVASCRIPT) | MIN STACKAndy Gala · 12:00 · 4K views
[Java] Leetcode 155. Min Stack [Stack & Queue #4]Eric Programming · 6:35 · 2K views
Min Stack | LeetCode 155 (Medium)Destination FAANG · 9:15 · 1K views
The problem
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.
Approach overview
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.
Approach 1: Using two stacks
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.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]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);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}#include <stack>
#include <climits>
class MinStack {
std::stack<int> s;
std::stack<int> minStack;
public:
MinStack() {
}
void push(int val) {
s.push(val);
if (minStack.empty() || val <= minStack.top()) {
minStack.push(val);
}
}
void pop() {
if (s.top() == minStack.top()) {
minStack.pop();
}
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return minStack.top();
}
};var MinStack = function() {
this.stack = [];
this.minStack = [];
};
MinStack.prototype.push = function(val) {
this.stack.push(val);
if (this.minStack.length == 0 || val <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(val);
}
};
MinStack.prototype.pop = function() {
if (this.stack.pop() === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
};
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
MinStack.prototype.getMin = function() {
return this.minStack[this.minStack.length - 1];
};#include <stdio.h>
#include <limits.h>
#define MAX_SIZE 30000
typedef struct {
int data[MAX_SIZE];
int minData[MAX_SIZE];
int top;
int minTop;
} MinStack;
MinStack* minStackCreate() {
MinStack* stack = (MinStack*)malloc(sizeof(MinStack));
stack->top = -1;
stack->minTop = -1;
return stack;
}
void minStackPush(MinStack* obj, int val) {
obj->data[++obj->top] = val;
if (obj->minTop == -1 || val <= obj->minData[obj->minTop]) {
obj->minData[++obj->minTop] = val;
}
}
void minStackPop(MinStack* obj) {
if (obj->top == -1) return;
if (obj->data[obj->top] == obj->minData[obj->minTop]) {
obj->minTop--;
}
obj->top--;
}
int minStackTop(MinStack* obj) {
return obj->data[obj->top];
}
int minStackGetMin(MinStack* obj) {
return obj->minData[obj->minTop];
}
void minStackFree(MinStack* obj) {
free(obj);
}using System.Collections.Generic;
public class MinStack {
private Stack<int> stack;
private Stack<int> minStack;
public MinStack() {
stack = new Stack<int>();
minStack = new Stack<int>();
}
public void Push(int val) {
stack.Push(val);
if (minStack.Count == 0 || val <= minStack.Peek())
minStack.Push(val);
}
public void Pop() {
if (stack.Peek() == minStack.Peek())
minStack.Pop();
stack.Pop();
}
public int Top() {
return stack.Peek();
}
public int GetMin() {
return minStack.Peek();
}
}The 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.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.
Approach 2: Using a single stack with tuple pairs
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.
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
if not self.stack:
self.stack.append((val, val))
else:
self.stack.append((val, min(val, self.stack[-1][1])))
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]import java.util.Stack;
class MinStack {
private Stack<int[]> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new int[]{val, val});
} else {
int currentMin = Math.min(val, stack.peek()[1]);
stack.push(new int[]{val, currentMin});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}#include <stack>
#include <climits>
class MinStack {
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;
}
};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.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), given two fields (value, min) for each element.
Approach 3: Default Approach
class MinStack {
stk1: number[];
stk2: number[];
constructor() {
this.stk1 = [];
this.stk2 = [Infinity];
}
push(val: number): void {
this.stk1.push(val);
this.stk2.push(Math.min(val, this.stk2[this.stk2.length - 1]));
}
pop(): void {
this.stk1.pop();
this.stk2.pop();
}
top(): number {
return this.stk1[this.stk1.length - 1];
}
getMin(): number {
return this.stk2[this.stk2.length - 1];
}
}
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/type MinStack struct {
stk1 []int
stk2 []int
}
func Constructor() MinStack {
return MinStack{[]int{}, []int{math.MaxInt32}}
}
func (this *MinStack) Push(val int) {
this.stk1 = append(this.stk1, val)
this.stk2 = append(this.stk2, min(val, this.stk2[len(this.stk2)-1]))
}
func (this *MinStack) Pop() {
this.stk1 = this.stk1[:len(this.stk1)-1]
this.stk2 = this.stk2[:len(this.stk2)-1]
}
func (this *MinStack) Top() int {
return this.stk1[len(this.stk1)-1]
}
func (this *MinStack) GetMin() int {
return this.stk2[len(this.stk2)-1]
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/use std::collections::VecDeque;
struct MinStack {
stk1: VecDeque<i32>,
stk2: VecDeque<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MinStack {
fn new() -> Self {
Self {
stk1: VecDeque::new(),
stk2: VecDeque::new(),
}
}
fn push(&mut self, x: i32) {
self.stk1.push_back(x);
if self.stk2.is_empty() || *self.stk2.back().unwrap() >= x {
self.stk2.push_back(x);
}
}
fn pop(&mut self) {
let val = self.stk1.pop_back().unwrap();
if *self.stk2.back().unwrap() == val {
self.stk2.pop_back();
}
}
fn top(&self) -> i32 {
*self.stk1.back().unwrap()
}
fn get_min(&self) -> i32 {
*self.stk2.back().unwrap()
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Min Stack easy or hard?
Min Stack is generally classified as a Medium problem. The individual operations are simple, but the challenge is designing the structure so getMin works in constant time without iterating through the stack.
How to solve Min Stack in O(1)?
Maintain the current minimum during each push operation instead of computing it later. With the two-stack approach, push the value to the main stack and update a min stack whenever the new value becomes the smallest. Alternatively, store pairs of (value, currentMin) in a single stack so the minimum is always accessible in constant time.
Min Stack Python or Java solution
In Python or Java, the typical implementation uses two stacks or a single stack storing pairs. Python often uses tuples like (value, min_so_far), while Java commonly uses a custom class or int array pair. Both approaches keep all operations in O(1) time.
What is the best approach for Min Stack?
The most common solution uses two stacks: one for normal stack values and another to track the minimum values. Every push updates the min stack when a new minimum appears, and getMin simply returns the top of the min stack. All operations run in O(1) time with O(n) additional space.
What data structure is used in Min Stack?
The primary data structure is a stack, typically implemented with an array or linked list. The optimized solution augments it with either a second stack to track minimum values or by storing (value, minimum) pairs in each stack node.
What is the time complexity of Min Stack?
A properly designed Min Stack supports push, pop, top, and getMin in O(1) time. This is achieved by maintaining extra state (such as a secondary min stack or storing the minimum with each element) so the minimum value never requires scanning the stack.
Is Min Stack asked at Google, Amazon, or Meta?
Min Stack is a common data structure design interview question and has appeared in interviews at companies like Amazon, Google, and Meta. It tests your understanding of stacks, constant-time operations, and how to augment a data structure with additional metadata.