Problem. Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.
This is the classic augmented stack design pattern.
Examples:
- After pushing
-2,0,-3,get_min()→-3 - After popping once from that stack,
top()→0 - After that pop,
get_min()→-2
Solution. Store each pushed value together with the minimum value seen up to that point. Then the top entry always knows the correct current minimum.
class MinStack:
def __init__(self):
self.stack = []
def push(self, val):
current_min = val if not self.stack else min(val, self.stack[-1][1])
self.stack.append((val, current_min))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def get_min(self):
return self.stack[-1][1]
All operations are O(1) time; the stack uses O(n) space.
Gotchas.
- Tracking only one global minimum breaks when that minimum is popped.
- A second dedicated min-stack is equally valid.
- Be clear about whether empty-stack operations are allowed; the standard version assumes valid calls.