Min Stack
Medium · Stack
Design a stack data structure that supports the usual push and pop operations but can also report the current minimum value in the stack in constant time. Implement push(val) to add a value, pop() to remove the most recently added value, top() to view the most recently added value, and getMin() to return the smallest value currently stored, all without scanning the whole stack. Calls to pop, top, and getMin will never be made on an empty stack.
Examples
Input: push(3), push(1), push(5), getMin(), pop(), top(), getMin()
Output: null, null, null, 1, null, 3, 1
Why: After pushing 3, 1, 5 the minimum is 1; popping removes 5, leaving 3 on top and 1 still the minimum.Input: push(-2), push(0), push(-3), getMin(), pop(), getMin()
Output: null, null, null, -3, null, -2
Why: The smallest value -3 is reported until it is popped, after which -2 becomes the new minimum.Constraints
-2^31 <= val <= 2^31 - 1, at most 3*10^4 calls total, pop/top/getMin are only called on a non-empty stack
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Min Stack. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.