Intuition
The minimum only changes when you push something smaller or pop the current champion. So store, alongside each element, the minimum as of that element — pop automatically restores the older minimum. History travels with the stack.
When a structure must report an aggregate in O(1), store the aggregate alongside each entry instead of recomputing it. Each frame remembers the minimum as of that push, so popping restores the previous minimum for free — no recalculation, no auxiliary scan. The same idea gives you a max-stack or a stack that tracks running sums.
Approach
Pair each entry with a running min
Push (x, min(x, current_min)). Top of stack always knows the whole stack's minimum.
Pop restores for free
Removing the top removes its snapshot too — the next pair's min was computed without it.
Two-stack variant
A second stack holding only new minima saves space when minima are rare; same idea.
Solution & live demo
Common pitfalls
Keeping a single min variable
def push(self, val):
self.stack.append(val)
self.min = min(self.min, val)
def pop(self):
self.stack.pop()m = min(val, self.stack[-1][1]) if self.stack else val self.stack.append((val, m))
Popping the current minimum leaves self.min pointing at a value that is no longer in the stack, and there is no way to recover the previous one without scanning. History has to be stored per frame, because popping must undo it.
Recomputing the minimum on demand
def getMin(self):
return min(self.stack)def getMin(self):
return self.stack[-1][1]Correct but O(n) per call, and the problem explicitly asks for constant time on every operation. The minimum was already known at push time — storing it turns the query into a lookup.
Seeding the minimum with zero
self.min = 0
m = val if not self.stack else min(val, self.stack[-1][1])
Zero is a real value that beats any positive input, so a stack of [3, 5] would report a minimum of 0 — a number never pushed. The first element's minimum is itself.
Edge cases
Guard empty; problem guarantees valid calls.
Each copy snapshots itself as min, so popping one still leaves the other's snapshot correct.