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 . (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.