A stack that also reports its smallest value in constant time. Store each push next to the minimum at that moment, so popping brings the old minimum back.
▼The problem
LeetCode 155 (Medium). Design a stack that supports push, pop, top and getMin, each in O(1) time.
Example: push 5, push 3, push 7, push 2 → getMin = 2; pop → getMin = 3; pop, pop → getMin = 5.
TRY IT ON LEETCODE ▶The solution
class MinStack:
def __init__(self):
self.stack = [] # (val, min) pairs
def push(self, val):
low = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, low))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def getMin(self):
return self.stack[-1][1]Transcript
Min Stack. Design a stack that can push, pop, read the top, and report the smallest value, all in constant time.
Push five, three, seven, then two. The minimum is two. Pop the two, and the minimum is three again. Pop twice more, and it's five.
The slow way scans the whole stack for every minimum: n steps per question. Or keep one min variable. It works while you push, but pop the two and the variable still says two. The real minimum is three, and the variable lost it.
The fix: when a crate goes on the stack, tag it with the minimum so far, the smaller of its value and the tag below it. Every crate then remembers the minimum of everything beneath it, so get min just reads the top tag.
In code, the stack holds pairs. Push adds the value with the smaller of it and the top's minimum. Pop removes the top pair. Top and get min read the two halves of the top pair.
Watch the tags. Five gets five. Three gets three. Seven keeps three. Two gets two. Get min: two. Pop it, and the crate below already says three. Pop seven, pop three, and five says five.
Every operation touches only the top, so each is constant time. The tags take one extra number per crate, so the space is order n.
Each crate remembers the minimum below it. That's Min Stack.