Min Stack (Design Data Structures)
Min Stack is a medium design data structures problem solved with the stack pattern.
The best approach, encoded values (one stack, one min variable), runs in O(1) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from second stack of minimums up.
Problem
Design a stack with push, pop, top and getMin, all in O(1). This is the Design module’s version: go beyond the pair-per-element solution and learn the single-stack encoding trick.
Examples
Example 1
- Input
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()- Output
-3, 0, -2
Constraints
- Every operation in O(1).
- pop, top and getMin are called only on a non-empty stack.
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 10 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 |
|---|---|---|
| Second stack of minimums | O(1) | O(n) |
| Encoded values (one stack, one min variable) | O(1) | O(n) |
1Second stack of minimums
O(1)O(n)Push onto a min stack only when the value is <= the current minimum; pop from it when the popped value equals the minimum.
- push: stack.push(v); if min empty or v <= min.peek(), min.push(v).
- pop: if stack.pop() == min.peek(), min.pop().
class MinStack {
private final Deque<Integer> st = new ArrayDeque<>(), mins = new ArrayDeque<>();
public void push(int val) {
st.push(val);
if (mins.isEmpty() || val <= mins.peek()) mins.push(val);
}
public void pop() {
if (st.pop().equals(mins.peek())) mins.pop();
}
public int top() { return st.peek(); }
public int getMin() { return mins.peek(); }
}class MinStack:
def __init__(self):
self.st = []
self.mins = []
def push(self, val: int) -> None:
self.st.append(val)
if not self.mins or val <= self.mins[-1]:
self.mins.append(val)
def pop(self) -> None:
if self.st.pop() == self.mins[-1]:
self.mins.pop()
def top(self) -> int:
return self.st[-1]
def getMin(self) -> int:
return self.mins[-1]class MinStack {
stack<int> st, mins;
public:
void push(int val) {
st.push(val);
if (mins.empty() || val <= mins.top()) mins.push(val);
}
void pop() {
int t = st.top();
st.pop();
if (t == mins.top()) mins.pop();
}
int top() { return st.top(); }
int getMin() { return mins.top(); }
};class MinStack {
constructor() {
this.st = [];
this.mins = [];
}
push(val) {
this.st.push(val);
if (this.mins.length === 0 || val <= this.mins[this.mins.length - 1]) this.mins.push(val);
}
pop() {
if (this.st.pop() === this.mins[this.mins.length - 1]) this.mins.pop();
}
top() { return this.st[this.st.length - 1]; }
getMin() { return this.mins[this.mins.length - 1]; }
}2Encoded values (one stack, one min variable)
O(1)O(n)One stack; no second stack of minimums.Keep min separately. When pushing v < min, push 2v - min (which is below v) and set min = v. On pop, if the top is below min, it was encoded: restore the old min as 2·min - top. The stack stores longs to avoid overflow.
- push: empty → push v, min = v. v >= min → push v. Else push 2v - min; min = v.
- pop: t = pop(); if t < min, min = 2·min - t.
- top: t < min ? min : t.
class MinStack {
private final Deque<Long> st = new ArrayDeque<>();
private long min;
public void push(int val) {
if (st.isEmpty()) { st.push((long) val); min = val; }
else if (val >= min) st.push((long) val);
else { st.push(2L * val - min); min = val; }
}
public void pop() {
long t = st.pop();
if (t < min) min = 2 * min - t;
}
public int top() {
long t = st.peek();
return (int) (t < min ? min : t);
}
public int getMin() { return (int) min; }
}class MinStack:
def __init__(self):
self.st = []
self.min = 0
def push(self, val: int) -> None:
if not self.st:
self.st.append(val)
self.min = val
elif val >= self.min:
self.st.append(val)
else:
self.st.append(2 * val - self.min)
self.min = val
def pop(self) -> None:
t = self.st.pop()
if t < self.min:
self.min = 2 * self.min - t
def top(self) -> int:
t = self.st[-1]
return self.min if t < self.min else t
def getMin(self) -> int:
return self.minclass MinStack {
stack<long long> st;
long long min;
public:
void push(int val) {
if (st.empty()) { st.push((long long) val); min = val; }
else if (val >= min) st.push((long long) val);
else { st.push(2LL * val - min); min = val; }
}
void pop() {
long long t = st.top();
st.pop();
if (t < min) min = 2 * min - t;
}
int top() {
long long t = st.top();
return (int) (t < min ? min : t);
}
int getMin() { return (int) min; }
};class MinStack {
constructor() {
this.st = [];
this.min = 0;
}
push(val) {
if (this.st.length === 0) { this.st.push(val); this.min = val; }
else if (val >= this.min) this.st.push(val);
else { this.st.push(2 * val - this.min); this.min = val; }
}
pop() {
const t = this.st.pop();
if (t < this.min) this.min = 2 * this.min - t;
}
top() {
const t = this.st[this.st.length - 1];
return t < this.min ? this.min : t;
}
getMin() { return this.min; }
}Edge cases to test
- Pushing the current minimum again, then popping one copy
- Values near Integer.MIN_VALUE (the encoding trick needs long)
Hints
Hint 1
Seen in the Stack module with a pair per element. Here, try the O(1)-extra-space version: store an encoded value when a new minimum arrives.
FAQ
What is the best time complexity for Min Stack?
Encoded values (one stack, one min variable) runs in O(1) time and O(n) extra space.
Which pattern does Min Stack use?
It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Design a Stack With Increment Operation, Maximum Frequency Stack, Max Stack.
Is there a brute force solution for Min Stack?
Yes. Second stack of minimums takes O(1) time and O(n) space. Push onto a min stack only when the value is <= the current minimum; pop from it when the popped value equals the minimum.
Which edge cases should I test for Min Stack?
Pushing the current minimum again, then popping one copy; Values near Integer.MINVALUE (the encoding trick needs long).