Min Stack
Problem statement
Build a stack that supports the usual push, pop and top operations,
plus one more: getMin, which returns the smallest value currently on the
stack. Every one of these four operations must run in O(1) time — you're not
allowed to scan the whole stack to answer getMin.
Implement a MinStack class with:
push(value)— addsvalueto the top of the stack.pop()— removes the element on top of the stack.top()— returns the element on top of the stack.getMin()— returns the smallest element currently in the stack.
Think of it as a stack that always knows its own running minimum, the way a monitoring dashboard might keep a running "lowest free memory seen so far" figure that updates instantly as new readings come in and old ones get discarded.
Examples
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() creates an empty stack. push(-2), push(0), push(-3) leave the stack holding -2, 0, -3 from bottom to top. getMin() returns -3, the smallest of the three. pop() removes -3, leaving -2 and 0. top() returns 0, the new top. getMin() now returns -2, the smallest of what's left.
Hints
push, pop and top for free — the only new problem is answering "what's the minimum?" instantly, without looking through the whole stack.Approach
Optimal: Single stack, encoded minimum
Intuition
The two-stack approach works, but it stores a full running-minimum value
next to every single element, even though the minimum usually doesn't
change from one push to the next. Instead, keep only one stack, and one
variable, minVal, for the current minimum. Most pushes just store the
value as normal. But when a value arrives that's smaller than minVal,
instead of also remembering the old minimum somewhere else, encode it
directly into the number you push: store 2 * value - minVal, then update
minVal to the new value. That stored number comes out smaller than the new
minVal, which is exactly the signal pop needs later: if the value you
just popped is less than the current minVal, it wasn't a real value at
all — it's a marker, and the real previous minimum can be recovered from it
with 2 * minVal - poppedValue, undoing the same arithmetic.
Steps
- Keep one stack and a variable
minVal. push(value): if the stack is empty, pushvalueand setminVal = value. Otherwise, ifvalue >= minVal, pushvalueas-is. Ifvalue < minVal, push2 * value - minVal(a marker smaller than the new minimum) and setminVal = value.pop(): pop the top of the stack. If that popped number is less thanminVal, it was a marker — recover the previous minimum withminVal = 2 * minVal - poppedValue.top(): look at the top of the stack without removing it. If it's less thanminVal, it's a marker, so the real top value isminValitself; otherwise the value on top is the real value.getMin()just returnsminVal.
Dry run
push(-2), push(0), push(-3):
| call | stack | minVal | what happened |
|---|---|---|---|
| push(-2) | [-2] | -2 | stack was empty → store -2 as-is |
| push(0) | [-2, 0] | -2 | 0 ≥ -2 → store 0 as-is |
| push(-3) | [-2, 0, -9] | -3 | -3 < -2 → store 2·(-3) - (-2) = -9, minVal becomes -3 |
getMin() returns minVal, -3. pop() pops -9; since -9 < the current
minVal (-3), it's a marker, so minVal is restored with
2 * minVal - top = 2 * (-3) - (-9) = -6 + 9 = -2 — its value before the
-3 was pushed — and the stack is now [-2, 0].
top() reads 0 directly (0 ≥ minVal, not a marker). getMin() returns
minVal, -2 — the same answers as both earlier approaches.
Edge cases: this trick works with negative numbers exactly the same way as
positive ones, since it's plain arithmetic rather than anything relying on
sign. With values near the very edges of a 32-bit range, 2 * value can
overflow a 32-bit integer, so the Java and C++ versions below carry the
stack and minVal in a wider integer type to stay correct at the
constraints' limits; Python integers don't have this problem.
Complexity
Time Every - operation is still O(1) — the same as the two-stack version, just with less memory per element.
Space O(n) - for the one stack of values, plus a single extra variable for the current minimum — no second stack the size of the first.
class MinStack:
def __init__(self):
self.stack = []
self.min_val = None
def push(self, val: int) -> None:
if not self.stack:
self.stack.append(val)
self.min_val = val
elif val >= self.min_val:
self.stack.append(val)
else:
self.stack.append(2 * val - self.min_val)
self.min_val = val
def pop(self) -> None:
top = self.stack.pop()
if top < self.min_val:
self.min_val = 2 * self.min_val - top
def top(self) -> int:
top = self.stack[-1]
return self.min_val if top < self.min_val else top
def getMin(self) -> int:
return self.min_val
if __name__ == "__main__":
s = MinStack()
out = [None]
s.push(-2); out.append(None)
s.push(0); out.append(None)
s.push(-3); out.append(None)
out.append(s.getMin())
s.pop(); out.append(None)
out.append(s.top())
out.append(s.getMin())
print(out)RecapThe whole problem in a few lines, for the night before
- Spot it: a stack that must also return its minimum in constant time
- Idea: store the minimum so far next to every pushed value (or keep a second stack of minimums)
- Cost: O(1) per operation, O(n) space
- Trap: after a pop the minimum must go back to the earlier one; a single
minvariable forgets it
Interview follow-ups
Extend it to also support
getMax()in O(1).Run the same idea twice, independently: keep a second running value
maxValalongsideminVal, and a second encoding rule for pushes that exceed it (for the two-stack version, a secondmaxStackmirroringstack). The two trackers don't interact — a value can update the minimum, the maximum, both, or neither, and each is maintained with the same push/pop logic as its own counterpart.What if you need
getMin()over only the last k pushed elements, not the whole stack?That's a different problem — a sliding-window minimum instead of a whole-stack minimum, since elements now need to expire after k more pushes rather than only on an explicit
pop. A monotonic deque (increasing from front to back) that also tracks each entry's "age" and evicts anything older than k pushes handles that in amortized O(1) per push, but it no longer maps onto a plain stack the way this problem does.
Frequently asked questions
It's the natural first idea and the easiest one to get right, so it's worth writing and testing before reaching for something cleverer — and it's a useful baseline to compare the faster approaches against. In an actual interview, you'd say up front that it doesn't meet the stated requirement and use it only as a stepping stone to the two-stack version.
Time and space are separate costs. Every operation being O(1) only means
each individual call does a bounded, constant amount of work — it says
nothing about how much memory the whole structure uses. minStack mirrors
stack entry for entry, so together they still need memory proportional to
how many values are on the stack.
It halves the memory compared to the two-stack version (one stack instead of two of the same size), which matters when the stack can hold up to 3 × 10⁴ values or more. In an interview, mentioning the two-stack solution first and then the single-stack refinement as a memory optimization shows you understand the space/time trade-off, which is often more valuable than jumping straight to the cleverest version.
A running minimum with instant push/pop shows up whenever you're tracking a "worst value so far" over a shrinking and growing window — lowest free disk space seen during a deploy, or the smallest available capacity across a rolling set of active nodes — without wanting to rescan everything on every check.