Quant Memo
Coding/●●●●●

Design a min-stack

Design a stack supporting push, pop, top, and get_min, retrieve the minimum element currently in the stack, with every operation in O(1)O(1). (Picture tracking the session low of a price series that can also "un-happen" when late corrections retract ticks.)

s = MinStack()
s.push(5); s.push(3); s.push(7)
s.get_min() -> 3
s.pop()                 # removes 7
s.get_min() -> 3
s.pop()                 # removes 3
s.get_min() -> 5

The catch: after popping the current minimum, the previous minimum must be recoverable instantly, a single min_so_far variable can't do that.

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions