02
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.
03
Approach
1
Pair each entry with a running min
Push (x, min(x, current_min)). Top of stack always knows the whole stack's minimum.
2
Pop restores for free
Removing the top removes its snapshot too — the next pair's min was computed without it.
3
Two-stack variant
A second stack holding only new minima saves space when minima are rare; same idea.
04
Solution & live demo
python
▶1class MinStack:
▶2 def __init__(self):
▶3 self.stack = [] # (value, min_so_far)
▶4
▶5 def push(self, val):
▶6 m = min(val, self.stack[-1][1]) if self.stack else val
▶7 self.stack.append((val, m))
▶8
▶9 def pop(self):
▶10 self.stack.pop()
▶11
▶12 def top(self):
▶13 return self.stack[-1][0]
▶14
▶15 def getMin(self):
▶16 return self.stack[-1][1]
05
Edge cases
getMin on fresh stack
Guard empty; problem guarantees valid calls.
Duplicate minima
Each copy snapshots itself as min, so popping one still leaves the other's snapshot correct.
06
Complexity
Time
O(1) all ops
Space
O(n)
One extra number per element.