Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path →
Min Stack
A stack that also returns its minimum in O(1) — no scanning. The trick is to carry the running minimum alongside each element. Replay a sequence of push/pop/top/getMin operations and return the outputs. Solve it in Python or TypeScript, with hidden tests.
The problem
Design a stack that supports push(x), pop(), top(), and getMin() — each in O(1) time. You are given a list of ops such as ["push",5], ["pop"], ["top"], ["getMin"]. Apply them in order and return the list of values produced by the read operations (top and getMin), in order.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? open the hints under the problem, or Reveal solution is one click away.
Implement min_stack_ops(ops): maintain a stack plus a parallel "min so far" stack. On push, record min(x, current_min); on pop, drop both. Collect the outputs of every top and getMin.
Examples and constraints 4 examples
ops = [["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]][3, 5, 5]ops = [["push",2],["push",2],["getMin"],["pop"],["getMin"]][2, 2]ops = [["push",3],["push",1],["pop"],["getMin"]][3]ops = [["push",5],["pop"],["push",7],["getMin"],["top"]][7, 7]- Every
pop/top/getMinis called on a non-empty stack. - All four operations must be O(1) — do not scan the stack to find the minimum.
- Duplicate minimum values must survive a single pop (the min only rises once all copies are gone).
Hints 4 ideas
- The naive getMin scans the stack — O(n). To get O(1), store the minimum as of each push next to the value.
- Keep a second stack
mins: when you pushx, pushmin(x, mins[-1])(or justxif empty). - On pop, pop both stacks together so
mins[-1]always reflects the current stack. - This is why duplicates matter: pushing the min twice puts it on
minstwice, so one pop does not lose it.
Approach, complexity & discussion — open after you solve
Start from brute force
The obvious approach keeps one plain stack and answers getMin with min(stack). It is correct, because the scan sees every value currently on the stack, and it needs no space beyond the stack itself: O(1) extra. But each getMin costs O(n) for n values on the stack, so a sequence of q operations can cost O(n · q); with 105 pushes followed by 105 reads that is 1010 comparisons, and the statement requires O(1). The other tempting shortcut, a single current_min variable, is fast but wrong: after push 3, push 1, pop it still says 1, because nothing remembers what the minimum was before the 1 arrived.
The approach
A stack only changes at its top, so the minimum of everything below the top cannot change while those values stay buried. That means the minimum can be computed once, at push time, and stored with the value. The invariant is mins[i] == min(stack[0..i]) for every level i, so mins[-1] is always the minimum of the whole stack, and popping a level restores exactly the minimum that held before it was pushed.
The reference solution keeps stack and mins the same length. On "push" it appends x to stack and x if not mins else min(x, mins[-1]) to mins; the empty check covers both the first push and any push after the stack has been emptied. On "pop" it pops both lists in lockstep. "top" appends stack[-1] to out and "getMin" appends mins[-1], so every operation is a constant number of list operations. Duplicates need no special case: pushing a second 2 appends another 2 to mins, so one pop cannot lose it.
mins stores the minimum of its own level and everything below it, computed once at push time. The reference on push 5, 3, 7, 2, getMin, pop, getMin, top returns [2, 3, 7]: the pop removes the dashed level from both stacks, and the level under it already holds the old minimum, 3, so nothing is recomputed.Walk through an example
Trace the first example, [["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]], watching mins mirror stack level for level.
| step | op | stack | mins | out |
|---|---|---|---|---|
| 1 | push 5 | [5] | [5] | [] |
| 2 | push 3 | [5, 3] | [5, 3] | [] |
| 3 | getMin | [5, 3] | [5, 3] | [3] |
| 4 | pop | [5] | [5] | [3] |
| 5 | getMin | [5] | [5] | [3, 5] |
| 6 | top | [5] | [5] | [3, 5, 5] |
Complexity
Optimal: O(1) time per operation, so O(q) for q operations, and O(n) space for the two parallel stacks of up to n values, plus the output. Brute force (scan on every getMin): O(n) per getMin, up to O(n · q) overall, with O(1) extra space.
Edge cases to test
- Duplicate minimums:
[["push",2],["push",2],["getMin"],["pop"],["getMin"]]→[2, 2]. A space-saving variant that pushes ontominsonly whenxis strictly smaller loses the second 2 and has nothing left after the pop. - Popping the minimum:
[["push",3],["push",1],["pop"],["getMin"]]→[3]. The previous minimum comes back, which a singlecurrent_minvariable cannot do. - Ascending pushes:
push 1, 2, 3givesmins = [1, 1, 1], so after apop,getMinis still1. - Emptying and refilling:
[["push",5],["pop"],["push",7],["getMin"],["top"]]→[7, 7]. Theif not minsbranch starts a fresh minimum instead of comparing with a value that is gone. - Negative values and zero:
[["push",-1],["push",0],["getMin"],["top"]]→[-1, 0]. Never use 0 as an “empty” sentinel for the minimum. - An empty-stack
pop,toporgetMinis ruled out by the constraints; the Python reference would raiseIndexErrorand the TypeScript one would returnundefined.
Common mistakes
- Recomputing the minimum by scanning the stack — that makes
getMinO(n) instead of O(1). - Forgetting to pop the min-stack alongside the main stack.
- Mishandling duplicate minimums — push the running min on every push (or handle ties explicitly) so a pop cannot lose the current min.
- Tracking the minimum in one variable, which cannot be restored after the minimum is popped.
Follow-ups an interviewer asks next
- Can you do it with O(1) extra space?
- Yes, by encoding. Keep one variable
m. When pushingxbelowm, push2x − minstead and setm = x; the stored value is below the new minimum, which marks it. On pop, a stored valueybelowmmeans the previous minimum was2m − y.topreturnsmfor a marked value. In fixed-width integers,2x − mcan overflow. - How would you save space when the minimum rarely changes?
- Push onto
minsonly whenx <= mins[-1], and pop it only when the popped value equalsmins[-1]. Pushing5, 6, 7, 8then stores one entry inminsinstead of four. The comparison must be<=, not<, or a duplicate minimum is popped away while a copy is still on the stack. - Can you build a queue that reports its minimum?
- Use two min-stacks: push onto an inbox, and pop from an outbox that is refilled by moving the whole inbox over when it runs empty. The queue’s minimum is the smaller of the two stacks’ minimums. Each element moves at most once, so every operation is amortized
O(1). For a fixed sliding window, a monotonic deque does the same job. - What if you also need the maximum?
- Add a third parallel stack,
maxs, maintained the same way withmax. The idea generalizes to any aggregate that can be combined from the value below: minimum, maximum, sum, and greatest common divisor all work. A median does not, because it cannot be computed from the previous median and one new value.
Where this shows up
“Carry an auxiliary aggregate alongside the structure” is the transferable idea — it scales to a max-stack, to min/max over a sliding window (a monotonic deque), and to running statistics. Min-stack is the smallest example of augmenting a data structure so an otherwise O(n) query becomes O(1).
Seen another way, mins is a prefix-minimum array that is maintained online: level i answers “what is the smallest value among the first i + 1 entries”. The same construction with sums instead of minimums gives a stack of running totals, and because subtraction undoes addition, that one answers more: the sum of the top k values is sums[-1] − sums[-1 − k], or just sums[-1] when k covers the whole stack. Minimum has no inverse, so a min-stack can only answer for the whole stack. That limitation is exactly why the min-queue follow-up needs two stacks rather than one: neither stack alone can report the minimum of an arbitrary middle range, but each can report the minimum of everything it holds.
The deeper pattern is that each level stores the state the structure had when that level was created, so popping is a perfect undo. Backtracking search uses this: a solver that pushes a frame per decision can store the best-so-far bound, or the count of constraints still open, in each frame, and abandoning a branch restores the earlier value for free. Union-find with rollback, used for offline dynamic connectivity, records each union on a stack so it can be reverted in order. Textbook data-structure courses formalize it as augmenting a structure: an order-statistic tree stores subtree sizes in every node so rank queries run in O(log n), for the same reason this stack stores minimums.
The cost is always the same trade, one extra field per element for a query that no longer scans. Whether to pay it depends on how often the query runs: a stack that is read for its minimum once in a million operations is better off scanning, which is what the brute force does.
Check yourself
What does min_stack_ops return for push 4, push 6, push 2, push 2, pop, getMin, pop, getMin, top?
[2, 4, 6]. After the pushes, mins is [4, 4, 2, 2]; the first pop leaves a 2 on top of mins, because the duplicate minimum was recorded twice, and the second pop exposes 4, the minimum of [4, 6], with 6 on top of the stack.
A bug pops stack but forgets to pop mins. What does it return for push 3, push 1, pop, getMin?
[1] instead of [3]. The 1 is gone from the stack but still on top of mins, so getMin reports a value that is no longer stored; every later answer is off too, because the two stacks no longer line up level for level.
With the space-saving rule, push onto mins only when x <= mins[-1], how many entries does mins hold after pushing 5, 6, 7, 8, 1, 1?
Three: [5, 1, 1], against six for the reference. The second 1 is recorded because the test is <=; with < it would be skipped, and popping one 1 would wrongly drop the minimum while the other 1 is still on the stack.
In the O(1)-space encoding, you push 5 and then 3. What is stored, and how does the pop of 3 recover the old minimum?
The stack stores [5, 1] with m = 3: 3 is below the minimum 5, so it is stored as 2·3 − 5 = 1. On pop, 1 is below m, which marks an encoded entry, and the previous minimum is 2·3 − 1 = 5.
Reference solution
Reference solution — Python
def min_stack_ops(ops):
stack = []
mins = [] # mins[i] = minimum of stack[0..i]
out = []
for op in ops:
kind = op[0]
if kind == "push":
x = op[1]
stack.append(x)
mins.append(x if not mins else min(x, mins[-1]))
elif kind == "pop":
stack.pop()
mins.pop() # keep the two stacks in lock-step
elif kind == "top":
out.append(stack[-1])
elif kind == "getMin":
out.append(mins[-1])
return out
print(min_stack_ops([["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]])) # -> [3, 5, 5]Reference solution — TypeScript
function minStackOps(ops: any[][]): number[] {
const stack: number[] = [];
const mins: number[] = []; // mins[i] = min of stack[0..i]
const out: number[] = [];
for (const op of ops) {
const kind = op[0];
if (kind === "push") {
const x = op[1] as number;
stack.push(x);
mins.push(mins.length ? Math.min(x, mins[mins.length - 1]) : x);
} else if (kind === "pop") {
stack.pop();
mins.pop(); // lock-step with the value stack
} else if (kind === "top") {
out.push(stack[stack.length - 1]);
} else if (kind === "getMin") {
out.push(mins[mins.length - 1]);
}
}
return out;
}
console.log(minStackOps([["push",5],["push",3],["getMin"],["pop"],["getMin"],["top"]])); // -> [3,5,5]Questions about Min Stack
How does a min stack return the minimum in O(1) time?
It stores the answer ahead of time. Alongside every value it pushes, it records the minimum of the stack at that moment, which is the smaller of the new value and the previous recorded minimum. Because a stack only ever changes at the top, those recorded minimums stay correct for every level below the top. Reading the minimum is then just reading the most recent record, and popping a value also pops its record, which brings back the minimum from before that value was pushed. Each operation is a constant number of list operations, so none of them depends on the stack size.
Why not just keep one variable for the minimum?
Because a single variable cannot be restored after the minimum is popped. Push 3 and then 1, and the variable correctly says 1. Pop the 1, and the true minimum is 3 again, but nothing in the variable remembers that 3 was the minimum before the 1 arrived; finding it would mean scanning the stack, which is O(n). The min stack solves this by keeping the minimum as of every level, so each pop hands back the previous answer. The space cost is one extra number per element, or less with the optimizations covered in the follow-ups.
Can a min stack be implemented with O(1) extra space?
Yes, with an encoding trick. Keep the current minimum m in one variable. When you push a value x smaller than m, store 2x minus m instead of x and set m to x. That stored number is smaller than the new minimum, which marks it as special. When you later pop a stored value y that is smaller than m, you know a minimum change happened at that level, and the previous minimum was 2m minus y. The top operation returns m whenever the stored value is marked. The catch is overflow in fixed-width integers, which Python avoids.
How does a min stack handle duplicate minimum values?
In the parallel-stack version shown here, duplicates need no special handling: every push records a minimum, so pushing 2 twice records 2 twice, and popping one copy leaves the other record in place. Duplicates become a trap in the space-saving variant that only records a new minimum when it changes. If that variant records only values strictly smaller than the current minimum, the second 2 is never recorded, and popping the first copy removes the only record while another 2 is still on the stack. Using less than or equal when deciding to record fixes it.
Explore the topic
See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.
More Challenges
- Two SumThe classic warm-up: find the two numbers that add up to a target. Brute force is O(n²) — a hash map gets you to one pass, O(n). Solve it in Python or TypeScript, right in your browser, with hidden tests and a reveal-solution button.Read →
- Valid ParenthesesThe canonical stack problem: decide whether every bracket is closed by the right type, in the right order. A stack turns nested matching into a single pass. Solve it in Python or TypeScript with hidden tests.Read →
- Fizz BuzzThe famous screening question. Print 1…n, but multiples of 3 become "Fizz", of 5 become "Buzz", and of both become "FizzBuzz". Easy — the catch is testing divisibility in the right order. Solve it in Python or TypeScript.Read →
- Number of IslandsThe canonical connected-components question. Flood-fill each unvisited patch of land with BFS or DFS, count how many floods you started — grid traversal, visited bookkeeping, and the classic diagonal trap. Solve it in Python or TypeScript.Read →
- Merge IntervalsCalendar apps and memory allocators run on this: sort by start, sweep once, grow or close the current block. Touching endpoints merge, nested intervals vanish — the classic that punishes off-by-one thinking. Solve it in Python or TypeScript.Read →
- Top-K Frequent ElementsCount, then rank — the two-step pattern behind trending topics and hot-key detection. A hash map counts; a (-count, value) sort ranks with a clean tie-break; buckets get you to O(n) if you want the flex. Solve it in Python or TypeScript.Read →