Min Stack — Solution in Python, Java & C++
Min Stack solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Min Stack is a medium coding problem on stack, asked in Amazon, Google, Microsoft and Bloomberg interviews.
- Difficulty: Medium
- Topics: Stack
- Asked at: Amazon, Google, Microsoft, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Design a stack that can also report its smallest element, with every operation in O(1) time. Write the class MinStack:
MinStack()creates an empty stack.void push(int x)pushesxonto the stack.void pop()removes the element on top of the stack.int top()returns the element on top of the stack.int getMin()returns the smallest element currently in the stack.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.
Example 1
Input: ["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation: After pushing -2, 0, -3 the minimum is -3. Popping -3 leaves 0 on top and -2 as the minimum again.
Example 2
Input: ["MinStack","push","push","push","getMin","pop","getMin","pop","getMin"]
[[],[4],[4],[7],[],[],[],[],[]]
Output: [null,null,null,null,4,null,4,null,4]
Explanation: Duplicates matter: with two 4s on the stack, popping one 4 still leaves a 4, so the minimum stays 4.
Constraints
-2^31 <= x <= 2^31 - 1pop, top and getMin are only called on a non-empty stackAt most 3 * 10^4 calls are made to push, pop, top and getMin
Hints for Min Stack
Hint 1
Keeping a single "current minimum" variable breaks as soon as the minimum is popped — what was the minimum before it?
Hint 2
The minimum of the stack depends only on what is below the top, and that never changes while the top is there.
Hint 3
Store, with every element, the minimum of the stack at the moment it was pushed:
min(x, previous minimum). ThengetMinreads it from the top entry.
How to solve Min Stack
Push pairs (x, minimum so far). The minimum of a stack is fixed by the elements in it, and the elements below the top never change while the top is in place, so the pair on top always carries the current minimum.
Approach
push(x): push(x, x)if the stack is empty, else(x, min(x, top.min)).pop(): pop the top pair.top(): return the top pair's value.getMin(): return the top pair's minimum.
Why it works
By induction, each pair's stored minimum is the minimum of itself and every element under it. Popping removes a pair without changing the pairs below, whose stored minima were computed from exactly the elements that remain.
Complexity
- Time —
O(1) per operation - Space —
O(n)
Pitfalls
- A separate min-stack that only records strictly smaller values breaks on duplicates of the minimum — record
<=values, or store the minimum with every element as here. - Values span the whole 32-bit range; avoid tricks like storing
x - min, which overflow in 32 bits.
Reference solution
Python
class MinStack:
def __init__(self):
self.st = [] # pairs (value, minimum of the stack up to here)
def push(self, x: int) -> None:
self.st.append((x, min(x, self.st[-1][1]) if self.st else x))
def pop(self) -> None:
self.st.pop()
def top(self) -> int:
return self.st[-1][0]
def getMin(self) -> int:
return self.st[-1][1]Java
class MinStack {
private Deque<int[]> st = new ArrayDeque<>(); // pairs {value, minimum up to here}
public MinStack() {
}
public void push(int x) {
st.push(new int[]{x, st.isEmpty() ? x : Math.min(x, st.peek()[1])});
}
public void pop() {
st.pop();
}
public int top() {
return st.peek()[0];
}
public int getMin() {
return st.peek()[1];
}
}C++
class MinStack {
vector<pair<int, int>> st; // {value, minimum up to here}
public:
MinStack() {}
void push(int x) {
st.push_back({x, st.empty() ? x : min(x, st.back().second)});
}
void pop() {
st.pop_back();
}
int top() {
return st.back().first;
}
int getMin() {
return st.back().second;
}
};JavaScript
var MinStack = function() {
this.vals = [];
this.mins = []; // mins[i] = minimum of vals[0..i]
};
MinStack.prototype.push = function(x) {
var n = this.mins.length;
this.vals.push(x);
this.mins.push(n === 0 ? x : Math.min(x, this.mins[n - 1]));
};
MinStack.prototype.pop = function() {
this.vals.pop();
this.mins.pop();
};
MinStack.prototype.top = function() {
return this.vals[this.vals.length - 1];
};
MinStack.prototype.getMin = function() {
return this.mins[this.mins.length - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 111 stack problems · the whole catalogue
Learn the technique: Stack Data Structure