Practice: Min Stack
The minimum in O(1).
Design a stack with push, pop, and one extra operation. Get min, which returns the smallest item in the stack, in O of one. Searching the stack would be O of N. Pause. What could you store alongside each item?

- push and pop
- Plus get_min
- All in O(1)
Store the minimum so far
The trick is to push pairs. Each item, together with the smallest value at that point. So the minimum is always on top, right next to the newest item. When we pop, the old minimum comes back automatically. Run it. The minimum goes from one, back to two.
class MinStack:
def __init__(self):
self.items = []
def push(self, x):
smallest = min(x, self.items[-1][1]) if self.items else x
self.items.append((x, smallest))
def pop(self):
return self.items.pop()[0]
def get_min(self):
return self.items[-1][1]
s = MinStack()
for x in [5, 2, 8, 1]:
s.push(x)
print("min:", s.get_min())
s.pop()
print("min after pop:", s.get_min())min: 1 min after pop: 2
Trading space for time
This is a common design pattern. We store a little extra information with each item, so a question that would need a search becomes a simple lookup. It doubles the memory, but every operation is O of one. The same idea works for a max stack.
| key | value |
|---|---|
| Push | store (item, min so far) |
| Pop | old min returns |
| get_min | top of the stack |
| Cost | O(1), extra memory |
Summary
Store the minimum so far with every item, and the minimum is always on top. Next, finding the middle of numbers that keep arriving.
Key takeaways- Push pairs
- Min is on top
- O(1) everything