Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack
class:
MinStack()
initializes the stack object.void push(int val)
pushes the element val
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int getMin()
retrieves the minimum element in the stack.You must implement a solution with O(1)
time complexity for each function.
Example 1:
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Constraints:
-231 <= val <= 231 - 1
pop
, top
and getMin
operations will always be called on non-empty stacks.3 * 104
calls will be made to push
, pop
, top
, and getMin
.This problem requires designing a stack data structure that supports push, pop, top, and getMin operations all in O(1) time complexity. A single stack is insufficient because finding the minimum element efficiently would require traversing the stack (O(n) time). The solution utilizes two stacks:
stk1
: This stack stores the actual elements pushed onto the min stack.stk2
: This stack stores the minimum element encountered so far at each point in time.Algorithm:
__init__
/Constructor
: Initializes both stacks. stk2
is initialized with a large value (infinity in Python, Integer.MAX_VALUE
in Java, etc.) to ensure the first element pushed will become the minimum.
push(val)
: When pushing a value val
:
val
onto stk1
.val
and the current minimum (top of stk2
) onto stk2
.pop()
: When popping an element:
stk1
and stk2
. This maintains the invariant that stk2
always reflects the minimum element seen so far after the pop operation.top()
: Returns the top element of stk1
.
getMin()
: Returns the top element of stk2
, which is the current minimum element in the stack.
Time and Space Complexity:
push
, pop
, top
, getMin
) have O(1) time complexity because they involve only stack operations (push and pop) which take constant time.Example Walkthrough (using Python):
Let's trace the example ["MinStack","push","push","push","getMin","pop","top","getMin"]
with [[],[-2],[0],[-3],[],[],[],[]]
:
MinStack()
: stk1 = []
, stk2 = [inf]
push(-2)
: stk1 = [-2]
, stk2 = [inf, -2]
push(0)
: stk1 = [-2, 0]
, stk2 = [inf, -2, -2]
push(-3)
: stk1 = [-2, 0, -3]
, stk2 = [inf, -2, -2, -3]
getMin()
: Returns -3
(top of stk2
)pop()
: stk1 = [-2, 0]
, stk2 = [inf, -2, -2]
top()
: Returns 0
(top of stk1
)getMin()
: Returns -2
(top of stk2
)This approach ensures that all operations are performed in O(1) time, fulfilling the requirements of the problem. The provided code snippets in different languages demonstrate this implementation. Note the slight variations in handling infinity/maximum integer values across different languages.