Min Stack
Implement MinStack with push(x), pop() and getMin(), all O(1). pop returns the removed value. On an empty stack, pop and getMin return undefined (None in Python, where the method is get_min).
push(5); push(3); push(7) getMin() -> 3 pop() -> 7 pop() -> 3 getMin() -> 5
Hints
Hint 1
Keep a second stack holding the minimum at each depth. Every push adds min(x, current minimum), and every pop removes one, so getMin is just its top.