Min Stack (Stack)
Min Stack is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (pair each value with the running minimum), runs in O(1) for every operation time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan for the minimum) up.
Problem
Design a stack that supports push, pop, top and getMin (return the smallest element currently in the stack), all in O(1) time.
Examples
Example 1
- Input
push(5), push(2), push(4), getMin(), pop(), pop(), getMin(), top()- Output
2, 5, 5- Why
- After popping 4 and 2, only 5 remains.
Constraints
-2^31 <= val <= 2^31 - 1- pop, top and getMin are only called on a non-empty stack.
- Every operation must be O(1).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (1 examples, or your own). Submit also runs 1 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan for the minimum) | O(1), getMin O(n) | O(n) |
| Optimal (pair each value with the running minimum) | O(1) for every operation | O(n) |
1Brute force (scan for the minimum)
O(1), getMin O(n)O(n)Use a normal stack and compute getMin by scanning every element.
- push, pop and top use the stack directly.
- getMin loops through all elements.
class MinStack {
private final Deque<Integer> st = new ArrayDeque<>();
public void push(int val) { st.push(val); }
public void pop() { st.pop(); }
public int top() { return st.peek(); }
public int getMin() {
int min = Integer.MAX_VALUE;
for (int x : st) min = Math.min(min, x);
return min;
}
}class MinStack:
def __init__(self):
self.st = []
def push(self, val: int) -> None:
self.st.append(val)
def pop(self) -> None:
self.st.pop()
def top(self) -> int:
return self.st[-1]
def getMin(self) -> int:
min_val = float("inf")
for x in self.st:
min_val = min(min_val, x)
return min_valclass MinStack {
vector<int> st;
public:
void push(int val) { st.push_back(val); }
void pop() { st.pop_back(); }
int top() { return st.back(); }
int getMin() {
int mn = INT_MAX;
for (int x : st) mn = min(mn, x);
return mn;
}
};class MinStack {
constructor() {
this.st = [];
}
push(val) { this.st.push(val); }
pop() { this.st.pop(); }
top() { return this.st[this.st.length - 1]; }
getMin() {
let min = Infinity;
for (const x of this.st) min = Math.min(min, x);
return min;
}
}2Optimal (pair each value with the running minimum)
O(1) for every operationO(n)Push pairs of (value, minimum so far). The top pair always knows the minimum of the whole stack, and popping restores the previous minimum automatically.
- push: newMin = min(val, current min); push {val, newMin}.
- top returns top[0]; getMin returns top[1]; pop removes the pair.
class MinStack {
private final Deque<int[]> st = new ArrayDeque<>();
public void push(int val) {
int min = st.isEmpty() ? val : Math.min(val, st.peek()[1]);
st.push(new int[] { val, min });
}
public void pop() { st.pop(); }
public int top() { return st.peek()[0]; }
public int getMin() { return st.peek()[1]; }
}class MinStack:
def __init__(self):
self.st = []
def push(self, val: int) -> None:
min_val = val if not self.st else min(val, self.st[-1][1])
self.st.append((val, min_val))
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]class MinStack {
vector<pair<int, int>> st;
public:
void push(int val) {
int mn = st.empty() ? val : min(val, st.back().second);
st.push_back({val, mn});
}
void pop() { st.pop_back(); }
int top() { return st.back().first; }
int getMin() { return st.back().second; }
};class MinStack {
constructor() {
this.st = [];
}
push(val) {
const min = this.st.length === 0 ? val : Math.min(val, this.st[this.st.length - 1][1]);
this.st.push([val, min]);
}
pop() { this.st.pop(); }
top() { return this.st[this.st.length - 1][0]; }
getMin() { return this.st[this.st.length - 1][1]; }
}Edge cases to test
- Pushing a value equal to the current minimum, then popping it
- Integer.MIN_VALUE as a value
Hints
Hint 1
Store with each element the minimum of the stack at the moment it was pushed.
FAQ
What is the best time complexity for Min Stack?
Optimal (pair each value with the running minimum) runs in O(1) for every operation time and O(n) extra space.
Which pattern does Min Stack use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Min Stack?
Yes. Brute force (scan for the minimum) takes O(1), getMin O(n) time and O(n) space. Use a normal stack and compute getMin by scanning every element.
Which edge cases should I test for Min Stack?
Pushing a value equal to the current minimum, then popping it; Integer.MINVALUE as a value.