Easy
Min Stack
👶 The 5-Year-Old Summary
You have a special box that holds a stack of numbers. Not only can you add and remove numbers, but it also tells you the smallest number in the whole box - instantly!
🎮 Interactive Visualizer
Try adding numbers and see how we track the minimum!
Main Stack:
Min Stack (tracking mins):
🧠The Brain Hack
The trick: keep TWO stacks! One for the actual values, and one that only keeps the minimums. When you push, also push to min-stack if it's <= current min. When you pop, pop from both!
💻 The Clean Solution
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
# Push to min_stack if it's empty or val is smaller
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
else:
# Otherwise repeat the current min
self.min_stack.append(self.min_stack[-1])
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
# Try it!
ms = MinStack()
ms.push(5)
ms.push(2)
ms.push(8)
print(ms.getMin()) # 2
ms.pop()
print(ms.getMin()) # 2
ms.pop()
print(ms.getMin()) # 5Time: O(1) for all operations!
Space: O(n) - extra stack for mins