Constant Time Min Stack
Problem
Design a stack that supports pushing a value, popping the top value, reading the top value, and reporting the smallest value currently stored. Every one of those operations must run in constant time, so scanning the contents to find the minimum is not acceptable. You may assume the minimum is only requested while the stack is non-empty.
Examples
Operations: push 5, push 2, push 7
minimum -> 2, top -> 7Operations: pop, pop (starting from the stack above)
minimum -> 5, top -> 5
Why: popping 2 must restore the earlier minimumOperations: push 3, push 3, pop
minimum -> 3
Why: edge case, duplicate minimums must survive one popHints
0 / 3
A single number holding the minimum breaks as soon as that minimum is popped, because the previous minimum is gone. The history has to be kept somehow.
Notice that the minimum only ever changes at push and pop time, and it changes in a last-in-first-out way, exactly matching the stack itself.
Alongside the values, maintain a parallel stack whose top always holds the minimum of everything below the matching level. On push, store the smaller of the new value and the current minimum. On pop, discard the top of both stacks together.
Solution
A second stack mirrors the main one, storing at each level the minimum of everything at or below that level. Pushing records the smaller of the incoming value and the previous minimum, so the mirror top is always the answer. Popping discards both tops together, which restores the earlier minimum automatically and handles duplicate minimums correctly. Every operation is O(1) time, and space is O(n) for the extra stack.
class MinStack:
def __init__(self): self.items, self.mins = [], [] # mins mirrors the running minimum
def push(self, x):
self.items.append(x)
# each level remembers the minimum of everything at or below it
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop() # both stacks always shrink together
return self.items.pop()
def top(self): return self.items[-1]
def minimum(self): return self.mins[-1]
s = MinStack()
for v in (5, 2, 7): s.push(v)
print(s.minimum(), s.top()) # -> 2 7
s.pop(); s.pop()
print(s.minimum(), s.top()) # -> 5 5Stuck on the idea rather than the code? Stack Basics covers it.