How does a min stack return the minimum in O(1)?

Keep a second stack that holds the minimum so far. Each push also records the current minimum, so after any pop the previous minimum is still on top.

What is the <= mistake everyone makes?

If the auxiliary stack only pushes on a strictly smaller value, duplicates of the minimum break it. Pushing when the new value is <= the current minimum keeps the counts in step.

What is the space cost?

O(n) extra in the worst case, since the auxiliary stack can grow as large as the main one. Pushing the minimum with every element is simpler and has the same bound.

Can it be done with a single stack?

Yes, by pushing pairs of (value, current minimum) or by encoding the previous minimum in the stored value. Pairs are easier to get right in an interview.

Why not scan the stack to find the minimum?

A scan is O(n) per query, and the whole point of the design is O(1) for push, pop, top and get_min.

What should happen when the stack is empty?

Decide and state it: raise an error or return a sentinel. Calling pop, top or get_min on an empty stack is the edge case interviewers check.

Design a stack that reports its minimum in O(1)

Q: What is the <= mistake everyone makes?

If the auxiliary stack only pushes on a strictly smaller value, duplicates of the minimum break it. Pushing when the new value is <= the current minimum keeps the counts in step.

Q: What is the space cost?

O(n) extra in the worst case, since the auxiliary stack can grow as large as the main one. Pushing the minimum with every element is simpler and has the same bound.

Q: Can it be done with a single stack?

Yes, by pushing pairs of (value, current minimum) or by encoding the previous minimum in the stored value. Pairs are easier to get right in an interview.

Q: Why not scan the stack to find the minimum?

A scan is O(n) per query, and the whole point of the design is O(1) for push, pop, top and get_min.

Q: What should happen when the stack is empty?

Decide and state it: raise an error or return a sentinel. Calling pop, top or get_min on an empty stack is the edge case interviewers check.

Interview QuestionsBy Ashish JangraUpdated 25 October 2026

Keep a second stack of minimums. On push, copy the value onto it whenever it is less than or equal to the current minimum; on pop, remove it from both if it was the top of both. min() is then one read. The <= is the whole question — strictly less breaks on duplicates.

Stacks & queuesCoding problemMedium

Step through it

Speed

What to watch

The min stack holds one entry per level at which the minimum changed, not one per element.
Pushing 1 twice pushes 1 onto the min stack twice — that is what <= buys.
After the pop, the minimum is still 1, because the second copy is underneath.

Say this out loud

"A second stack holding the minimum at each level. Push copies the value onto the min stack when it is less than or equal to the current minimum; pop removes it from the min stack if it matches. min() is the top of that stack, so it is O(1). The trap is using strictly less than, which loses a duplicate minimum on the first pop."

class MinStackBroken: def __init__(self): self.data, self.mins = [], [] def push(self, x): self.data.append(x) if not self.mins or x < self.mins[-1]: # STRICTLY less: the bug self.mins.append(x) def pop(self): v = self.data.pop() if self.mins and v == self.mins[-1]: self.mins.pop() return v def min(self): return self.mins[-1] class MinStack: def __init__(self): self.data, self.mins = [], [] def push(self, x): self.data.append(x) if not self.mins or x <= self.mins[-1]: # <= keeps one per duplicate self.mins.append(x) def pop(self): v = self.data.pop() if self.mins and v == self.mins[-1]: self.mins.pop() return v def top(self): return self.data[-1] def min(self): return self.mins[-1] for name, cls in (("strictly <", MinStackBroken), ("<= ", MinStack)): s = cls() for x in (2, 1, 1): # 1 pushed twice: the duplicate minimum s.push(x) s.pop() # remove one of the 1s print(f"{name} push 2,1,1 then one pop -> min() = {s.min()} (correct: 1)")

class MinStack: def __init__(self): self.data, self.mins = [], [] def push(self, x): self.data.append(x) if not self.mins or x <= self.mins[-1]: # <= keeps one per duplicate self.mins.append(x) def pop(self): v = self.data.pop() if self.mins and v == self.mins[-1]: self.mins.pop() return v def top(self): return self.data[-1] def min(self): return self.mins[-1] s = MinStack() for x in (5, 4, 6, 3, 7, 3): s.push(x) print("after pushing 5,4,6,3,7,3") print(" data:", s.data) print(" mins:", s.mins, "<- one entry per level where the minimum changed") ascending = MinStack() for x in (1, 2, 3, 4, 5): ascending.push(x) print() print("ascending input 1..5") print(" mins:", ascending.mins, "<- the best case: one entry")

class MinStack: def __init__(self): self.data, self.mins = [], [] def push(self, x): self.data.append(x) if not self.mins or x <= self.mins[-1]: # <= keeps one per duplicate self.mins.append(x) def pop(self): v = self.data.pop() if self.mins and v == self.mins[-1]: self.mins.pop() return v def top(self): return self.data[-1] def min(self): return self.mins[-1] class PairStack: def __init__(self): self.stack = [] def push(self, x): current = x if not self.stack else min(x, self.stack[-1][1]) self.stack.append((x, current)) def pop(self): return self.stack.pop()[0] def min(self): return self.stack[-1][1] values = (5, 4, 6, 3, 7, 3) two = MinStack(); pair = PairStack() for x in values: two.push(x); pair.push(x) print("pair variant stores:", pair.stack) print("same minimum:", pair.min() == two.min()) print() print("extra slots used for", len(values), "pushes:") print(" two stacks:", len(two.mins), "<- only when the minimum changed") print(" pairs :", len(pair.stack), "<- always one per element")

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Design a stack that reports its minimum in O(1)

Step through it

What to watch

Say this out loud

Overview

Run it

Why a scan is not allowed

The <= that everybody gets wrong first

The one-stack variants

What the question is testing

Edge cases to raise

Sources and next steps

How the code works

How the code works

Change one thing

Where this runs

Check yourself