Loading problem…
Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time complexity. Implement the MinStack class with these operations: push(val) pushes the element onto the stack, pop() removes the top element, top() returns the top element, and getMin() retrieves the minimum element in the stack.
Example 1
Input: operations = ["MinStack","push","push","push","getMin","pop","top","getMin"], arguments = [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation: After pushing -2, 0 and -3, the minimum is -3. pop() removes -3, so top() is 0 and the minimum goes back to -2.
Example 2
Input: operations = ["MinStack","push","push","getMin","pop","top","getMin"], arguments = [[],[2],[1],[],[],[],[]]
Output: [null,null,null,1,null,2,2]
Explanation: After pushing 2 and 1, the minimum is 1. pop() removes 1, leaving 2 as both the top and the minimum.
Example 3
Input: operations = ["MinStack","push","push","push","getMin","pop","getMin","pop","getMin"], arguments = [[],[1],[2],[0],[],[],[],[],[]]
Output: [null,null,null,null,0,null,1,null,1]
Explanation: After pushing 1, 2 and 0, the minimum is 0. Popping 0 makes the minimum 1, and popping 2 leaves it at 1.
`getMin` has to be O(1), but `min(stack)` is O(n). The trick: maintain a *second* stack that, at every moment, has the running minimum at its top. Push and pop in lockstep with the main stack and the top of the mins-stack is always exactly the minimum of the values currently in the main stack.
Run checks all cases above. Submit evaluates all test cases.