Design a stack that, in addition to the usual operations, can report its smallest element, and every operation must run in constant time:
push(val), putvalon top.pop(), remove the top element.top(), read the top element without removing it.getMin(), return the minimum value currently in the stack.
You can assume pop, top, and getMin are only called when the stack is
non-empty.
Examples
Input
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()Output
getMin() → -3, top() → 0, getMin() → -2With [-2, 0, -3] the min is -3. After popping the -3, the min must *revert* to -2. That reversion is the whole problem.
Constraints
-2³¹ ≤ val ≤ 2³¹ - 1At most 3 × 10⁴ operations totalpop, top, and getMin are never called on an empty stackEvery operation must be O(1)
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.