Min Stack

Medium · Stack & Monotonic Stack · about 15 minutes

Asked at Amazon, Bloomberg, Microsoft, Google.

Build a stack that, in addition to push, pop and top, can report the smallest value it currently holds via getMin. All four operations must run in O(1) time. pop, top and getMin are never called while the stack is empty.