Interview challenge · medium · stack, design
Min Stack
The challenge
Design a stack that supports push, pop, top and get_min, where get_min returns the smallest value currently in the stack. Every operation must run in O(1) time: no scanning the stack to find the minimum.
Example
push(-2), push(0), push(-3)
get_min() -> -3
pop() (removes -3)
top() -> 0
get_min() -> -2Idea: store each value together with the minimum of the stack at the moment it was pushed: the smaller of the new value and the minimum stored below it. The top entry then always knows the minimum of the whole stack, and popping it brings back the minimum of what is left, with no extra work. Every operation is O(1), at the cost of a second number per entry.
The solution
# Min Stack - ayotl.dev
class MinStack:
def __init__(self):
# each entry: (value, min so far)
self.s = []
def push(self, x):
m = x
if self.s:
m = min(x, self.get_min())
self.s.append((x, m))
def pop(self):
self.s.pop()
def top(self):
return self.s[-1][0]
def get_min(self):
return self.s[-1][1]
st = MinStack()
for x in [-2, 0, -3]:
st.push(x)
print("min", st.get_min())
st.pop()
print("top", st.top())
print("min", st.get_min())
$ python3 min_stack.py
min -3
top 0
min -2