Min Stack
Problem Description
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 elementvalonto 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
Constraints:
- -231 <= val <= 231 - 1
- Methods
pop,topandgetMinoperations will always be called on non-empty stacks. - At most
3 * 104calls will be made topush,pop,top, andgetMin.
Solve it on LeetCode
Approaches
1. Using Two Stacks
Intuition:
The idea here is to use two stacks. One stack will be used as a regular stack to store all the numbers, whereas the second stack (let's call it the minStack) will be used to keep track of the minimum value at each stage. Whenever we push an element, we'll also push the new minimum onto the minStack. When we pop an element, we'll also pop from the minStack to ensure both stacks stay synchronized.
Code:
- Time Complexity: O(1) for each operation (
push,pop,top, andgetMin). - Space Complexity: O(n) where n is the number of elements in the stack, since we are using two stacks.
2. Using Single Stack with Pair Value
Intuition:
Rather than using two separate stacks, we can optimize space by using a single stack, where each element in the stack is a pair consisting of the actual value and the minimum value up to that point.
Code:
- Time Complexity: O(1) for each operation.
- Space Complexity: O(n), but now we use only a single stack.
3. Single Stack with Min Tracking
Intuition:
Another approach is to keep track of the minimum value in a variable. We push new values onto the stack, and if a new value is the new minimum, we first push the previous minimum onto the stack and then push the new value. The main advantage of this approach is that we use a single stack and minimum variables to efficiently track the minimum value.
Code:
- Time Complexity: O(1) for each operation.
- Space Complexity: O(n), but more efficient stack utilization by storing the minimum only when necessary.