Medium Pair with Min Stacks & Queues
In plain English: Build a stack that also tells you the current minimum element in O(1) time.
Storing the running minimum alongside each value preserves the min history as elements are popped — no need to rescan.
Prompt
Design a stack that supports push, pop, and getMin in O(1).
Try to write it from scratch before scrolling down.
Solution
class MinStack:
def __init__(self):
self.stack = [] # stores (val, cur_min)
def push(self, x):
cur_min = min(x, self.stack[-1][1]) if self.stack else x
self.stack.append((x, cur_min)) # pair: (value, min-so-far)
def pop(self):
return self.stack.pop()[0]
def get_min(self):
return self.stack[-1][1]
# Test: push(3), push(1), push(5) => get_min() == 1