Min Stack
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.
Examples
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
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- At most 3 * 104 calls will be made to push, pop, top, and getMin.
We are given a design based problem statement, in design-based questions we need to figure out the algorithm for each of the module. Even though we are given to try to get a solution that achieves O(1) time complexity, we will first see the flow of the Brute Force Approach and then proceed for the Optimal Ones.
Brute Force Approach
Intuition
The problem description gives a straight-forward intuition of using a stack. If we read the problem statement carefully, we see that the we need to implement the push(int val), pop(), top(), and getMin() modules.
Funny but the push(), pop() and the top() functions are inbuilt in the programming languages that we are going to use. Our main focus is to implement the getMin() method.
The getMin() method involves the logic of retrieving the minimum of all the values present in the stack.
For a moment let's not build the logic in O(1) runtime. It's quite obvious that we have to traverse all the elements in the stack to find out the minimum element.
But unlike arrays, we cannot simply traverse the stack elements one by one. Stack says that we can only view the top of the stack and in order to traverse the next of the elements, we have to pop it. But we have to maintain the order as well. What can we do?
We will be using another stack let's say temp where we will pop the elements one by one from the main stack to temp and we will calculate the minimum element parallelly.
Why did we used another stack (temp) ?
When we popped elements from the main stack to temp, because when we again push it from the temp stack to the main stack, the order of elements is retained.
Approach
Initialize MinStack: Create a stack to store the elements.
Push(int val) Operation: Add the given value to the stack.
Pop() Operation: Remove the top element from the stack.
Top() Operation: Return the top element of the stack without removing it.
getMin() operation : Initialize a variable min with the maximum possible value. Create a temporary stack to help in the operation.
While the main stack is not empty:
- Compare the current top of the stack with min and update min to the smaller value.
- Transfer the top element of the stack to the temporary stack.
While the temporary stack is not empty:
- Transfer elements back to the main stack to restore its original order.
Return the value of min.
Dry-Run
Input Operations:
["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
Values:
[[], [5], [3], [7], [], [], [], []]
Output: [null, null, null, null, 3, null, 3, 3]
Initialize MinStack
- Stack: []
2. Push 5
- Add 5 to the stack.
- Stack: [5]
3. Push 3
- Add 3 to the stack.
- Stack: [5, 3]
4. Push 7
- Add 7 to the stack.
- Stack: [5, 3, 7]
5. Get Minimum
Initialize min as ∞.
Use a temporary stack to traverse and find the minimum:
- Pop 7 → Update min = min(∞, 7) = 7 → Push 7 into the temporary stack.
- Pop 3 → Update min = min(7, 3) = 3 → Push 3 into the temporary stack.
- Pop 5 → Update min = min(3, 5) = 3 → Push 5 into the temporary stack.
Restore original stack order: Pop from the temporary stack and push back into the main stack.
- Stack: [5, 3, 7]
- Minimum: 3
6. Pop
- Remove the top element 7.
- Stack: [5, 3]
7. Top
- Return the top element of the stack, which is 3.
- Output: 3
8. Get Minimum
Initialize min as ∞.
Use a temporary stack to traverse and find the minimum:
- Pop 3 → Update min = min(∞, 3) = 3 → Push 3 into the temporary stack.
- Pop 5 → Update min = min(3, 5) = 3 → Push 5 into the temporary stack.
Restore original stack order: Pop from the temporary stack and push back into the main stack.
- Stack: [5, 3]
- Minimum: 3
Final Output:
[null, null, null, null, 3, null, 3, 3]
Brute Force Code in all Languages.
1. C++ Try on Compiler
class MinStack {
// Declare the stack to store elements
stack<int> stack;
public:
// Constructor to initialize the stack
MinStack() {}
// Method to push a value onto the stack
void push(int val) {
// Add the value to the stack
stack.push(val);
}
// Method to pop the top value from the stack
void pop() {
// Remove the top value from the stack
stack.pop();
}
// Method to get the top value of the stack
int top() {
// Return the top value of the stack
return stack.top();
}
// Method to get the minimum value in the stack
int getMin() {
// Initialize min to a very large value
int min = INT_MAX;
// Create a temporary stack to store elements
stack<int> temp;
// Traverse through the stack to find the minimum value
while (!stack.empty()) {
// Update min with the smaller of min and the current top of the stack
min = std::min(min, stack.top());
// Add the current top of the stack to the temporary stack
temp.push(stack.top());
stack.pop();
}
// Restore all elements back to the original stack
while (!temp.empty()) {
stack.push(temp.top());
temp.pop();
}
// Return the minimum value found
return min;
}
};
2. Java Try on Compiler
class MinStack {
// Declare the stack to store elements
Stack<Integer> stack;
// Constructor to initialize the stack
public MinStack() {
// Initialize the stack
this.stack = new Stack<>();
}
// Method to push a value onto the stack
public void push(int val) {
// Add the value to the stack
stack.push(val);
}
// Method to pop the top value from the stack
public void pop() {
// Remove the top value from the stack
stack.pop();
}
// Method to get the top value of the stack
public int top() {
// Return the top value of the stack
return stack.peek();
}
// Method to get the minimum value in the stack
public int getMin() {
// Initialize min to a very large value
int min = Integer.MAX_VALUE;
// Create a temporary stack to store elements
Stack<Integer> temp = new Stack<>();
// Traverse through the stack to find the minimum value
while (!stack.isEmpty()) {
// Update min with the smaller of min and the current top of the stack
min = Math.min(min, stack.peek());
// Add the current top of the stack to the temporary stack
temp.add(stack.pop());
}
// Restore all elements back to the original stack
while (!temp.isEmpty()) {
stack.push(temp.pop());
}
// Return the minimum value found
return min;
}
}
3. Python Try on Compiler
class MinStack:
# Constructor to initialize the stack
def __init__(self):
self.stack = []
# Method to push a value onto the stack
def push(self, val):
# Add the value to the stack
self.stack.append(val)
# Method to pop the top value from the stack
def pop(self):
# Remove the top value from the stack
self.stack.pop()
# Method to get the top value of the stack
def top(self):
# Return the top value of the stack
return self.stack[-1]
# Method to get the minimum value in the stack
def getMin(self):
# Initialize min to a very large value
min_val = float('inf')
# Create a temporary list to store elements
temp = []
# Traverse through the stack to find the minimum value
while self.stack:
# Update min with the smaller of min and the current top of the stack
min_val = min(min_val, self.stack[-1])
# Add the current top of the stack to the temporary list
temp.append(self.stack.pop())
# Restore all elements back to the original stack
while temp:
self.stack.append(temp.pop())
# Return the minimum value found
return min_val
def main():
# Read the number of operations
n = int(input("Enter number of operations: "))
# Create a MinStack object
min_stack = MinStack()
# Perform operations based on input
for _ in range(n):
operation = input("Enter operation (push, pop, top, getMin) and value (if applicable): ").split()
if operation[0] == "push":
val = int(operation[1])
min_stack.push(val)
elif operation[0] == "pop":
min_stack.pop()
elif operation[0] == "top":
print(f"Top: {min_stack.top()}")
elif operation[0] == "getMin":
print(f"Min: {min_stack.getMin()}")
if __name__ == "__main__":
main()
4. JavaScript Try on Compiler
class MinStack {
// Constructor to initialize the stack
constructor() {
this.stack = [];
}
// Method to push a value onto the stack
push(val) {
// Add the value to the stack
this.stack.push(val);
}
// Method to pop the top value from the stack
pop() {
// Remove the top value from the stack
this.stack.pop();
}
// Method to get the top value of the stack
top() {
// Return the top value of the stack
return this.stack[this.stack.length - 1];
}
// Method to get the minimum value in the stack
getMin() {
// Initialize min to a very large value
let min = Infinity;
// Create a temporary array to store elements
const temp = [];
// Traverse through the stack to find the minimum value
while (this.stack.length > 0) {
// Update min with the smaller of min and the current top of the stack
min = Math.min(min, this.stack[this.stack.length - 1]);
// Add the current top of the stack to the temporary array
temp.push(this.stack.pop());
}
// Restore all elements back to the original stack
while (temp.length > 0) {
this.stack.push(temp.pop());
}
// Return the minimum value found
return min;
}
}
Time Complexity: O(n)
Push Operation (push(val)):
- Time complexity: O(1)
- Explanation: Pushing a value onto the stack takes constant time, as it only involves adding an element to the end of the stack.
Pop Operation (pop()):
- Time complexity: O(1)
- Explanation: Popping the top value from the stack is a constant-time operation, as it just removes the top element.
Top Operation (top()):
- Time complexity: O(1)
- Explanation: Accessing the top element of the stack is a constant-time operation because it involves looking at the last element.
Get Min Operation (getMin()):
- Time complexity: O(n)
- Explanation: The getMin() method involves iterating through the stack to find the minimum value, which takes linear time, O(n), where nnn is the number of elements in the stack. Additionally, it temporarily moves all elements to a new stack and back, which also takes O(n) time.
Total time complexity is: O(1) + O(1) + O(1) + O(n)= O(n)
Space Complexity: O(n)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
Push Operation (push(val)):
Auxiliary space complexity: O(1)
Explanation: No additional space is used for the push() operation, apart from the space required to store the value in the stack.
Pop Operation (pop()):
Auxiliary space complexity: O(1)
Explanation: No additional space is used for the pop() operation, apart from removing the top element from the stack.
Top Operation (top()):
Auxiliary space complexity: O(1)
Explanation: The top() operation does not use any extra space other than accessing the last element of the stack.
Get Min Operation (getMin()):
Auxiliary space complexity: O(n)
Explanation: The getMin() method uses a temporary stack to hold elements while it processes the original stack. The space used by the temporary stack is proportional to the number of elements in the stack, so it requires O(n) auxiliary space.
Total auxiliary space is O(n).
Total Space Complexity
- The main stack requires O(n) space, where n is the number of elements in the stack.
- The temporary stack used by the getMin() operation requires O(n) auxiliary space.
Thus, the total space complexity is O(n).
The Brute Force approach of using a stack was quite intuitive, but the getMin() function could have been a bit slower for higher constraints, can we think of a better approach.
Optimal Approach
Intuition
It was clear in the brute force approach that the getMin() function was slower since it involved the push and pop operations quite a number of times. This made the entire design a bit slower.
Let's take a scenario.
Imagine we are given few numbers one by one and we place the numbers on a shelf one upon other. We can only see the number at the top. At any moment can either be asked to remove the topmost number or we may be asked to tell the minimum number encountered till now.
How, can we perform this task ?? What we will do is we will maintain a record of the minimum numbers that are encountered from the very beginning.
When we are told the first number, its obvious that we will place the number on the shelf, but we will note down this number on the record because if there is only one element in the shelf, it's obvious that no other number can be minimum than that.
When we are given the second number we will put it again to the shelf but before updating the register , we must check is the previous number is greater than it or not. Suppose the register has the number 7 on it and we are given a number 10 to put on the shelf, shall we update the register and write 10?
No, because the register is used only for the purpose of maintaining the smallest element. There is no need to update the record instead we will just put the number on the shelf.
Let's suppose our shelf has numbers 10,12,8,7 (bottom to top order) and our record contains 10,8,7 . Now, we are asked to remove the top most element.
The top most element is 7.
We will simply remove 7 from the top. But, are we missing something. Can ther be a possibility that the number we are told to remove can be the minimum element encountered till now?
Yes, when we are told to remove the number we must check if the record contains that number on top or not. If it is, then we remove from the record as well.
Now, since we have figured out the logic and the algorithm behind the design task. What all data-structures to use?
We will maintain a stack (shelf as used above) , a minStack(record to maintain minimum element).
When, the push() is called we will push it to the stack and before pushing to the minStack we must check the top value of the minStack. The same conditions holds while popping the elements from the stack.
Whenever the getMin() function is called we will retrieve the top value of the minStack and return it.
Let's see how we can code it up !!
Approach
Initialize the MinStack:
Create two empty stacks: mainStack to hold all elements. minStack to hold the minimum elements.
push(x) - Add an element to the stack:
- Add x to the mainStack.
- If minStack is empty or x is less than or equal to the top of minStack: Add x to the minStack.
pop() - Remove the top element from the stack:
- If the top element of mainStack is equal to the top element of minStack: Remove the top element from minStack
- Remove the top element from mainStack.
top() - Retrieve the top element of the stack: Return the top element of mainStack.
getMin() - Retrieve the minimum element in the stack: Return the top element of minStack.
Dry-Run
Input Operations:
["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
Values:
[[], [5], [3], [7], [], [], [], []]
Output: [null, null, null, null, 3, null, 3, 3]
Execution Step-by-Step:
Operation: "MinStack"
Values: []
Action: Initialize the MinStack object with two empty stacks:
mainStack = []
minStack = []
Output: null
- Operation: "push"
Values: [5]
Action: Add 5 to mainStack. Since minStack is empty, also add 5 to minStack.
mainStack = [5]
minStack = [5]
Output: null
- Operation: "push"
Values: [3]
Action: Add 3 to mainStack. Since 3 is smaller than or equal to the top of minStack (5), also add 3 to minStack.
mainStack = [5, 3]
minStack = [5, 3]
Output: null
- Operation: "push"
Values: [7]
Action: Add 7 to mainStack. Since 7 is greater than the top of minStack (3), do not add it to minStack.
mainStack = [5, 3, 7]
minStack = [5, 3]
Output: null
- Operation: "getMin"
Values: []
Action: Return the top of minStack, which is 3.
Output: 3
- Operation: "pop"
Values: []
Action: Remove the top element from mainStack (7). Since 7 is not equal to the top of minStack (3), do not remove anything from minStack.
mainStack = [5, 3]
minStack = [5, 3]
Output: null
- Operation: "top"
Values: []
Action: Return the top of mainStack, which is 3.
Output: 3
- Operation: "getMin"
Values: []
Action: Return the top of minStack, which is 3.
Output: 3
Final Output:
[null, null, null, null, 3, null, 3, 3]
Optimal Code in all Languages.
1. C++ Try on Compiler
class MinStack {
private:
// Declare two stacks: one for elements and one for tracking minimums
stack<int> stack;
stack<int> minStack;
public:
/** Initialize your data structure here. */
MinStack() {
// Constructor initializes empty stacks
}
/** Push element x onto stack. */
void push(int x) {
// Add x to the main stack
stack.push(x);
// Add x to the min stack if it's empty or x <= top of minStack
if (minStack.empty() || x <= minStack.top()) {
minStack.push(x);
}
}
/** Removes the element on the top of the stack. */
void pop() {
// If the top of the main stack equals the top of the min stack, remove it from the min stack
if (stack.top() == minStack.top()) {
minStack.pop();
}
// Remove the top element from the main stack
stack.pop();
}
/** Get the top element. */
int top() {
// Return the top element of the main stack
return stack.top();
}
/** Retrieve the minimum element in the stack. */
int getMin() {
// Return the top element of the min stack
return minStack.top();
}
};
2. Java Try on Compiler
class MinStack {
// Declare two stacks: one for elements and one for tracking minimums
private Stack<Integer> stack;
private Stack<Integer> minStack;
/** Initialize your data structure here. */
public MinStack() {
// Initialize the main stack
stack = new Stack<>();
// Initialize the minimum stack
minStack = new Stack<>();
}
/** Push element x onto stack. */
public void push(int x) {
// Add x to the main stack
stack.push(x);
// Add x to the min stack if it's empty or x <= top of minStack
if (minStack.isEmpty() || x <= minStack.peek()) {
minStack.push(x);
}
}
/** Removes the element on the top of the stack. */
public void pop() {
// If the top of the main stack equals the top of the min stack, remove it from the min stack
if (stack.peek().equals(minStack.peek())) {
minStack.pop();
}
// Remove the top element from the main stack
stack.pop();
}
/** Get the top element. */
public int top() {
// Return the top element of the main stack
return stack.peek();
}
/** Retrieve the minimum element in the stack. */
public int getMin() {
// Return the top element of the min stack
return minStack.peek();
}
}
3. Python Try on Compiler
class MinStack:
def __init__(self):
# Initialize the main stack and the min stack
self.stack = []
self.min_stack = []
def push(self, x: int):
# Add x to the main stack
self.stack.append(x)
# Add x to the min stack if it's empty or x <= top of min_stack
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self):
# If the top of the main stack equals the top of the min stack, remove it from the min stack
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
# Remove the top element from the main stack
self.stack.pop()
def top(self) -> int:
# Return the top element of the main stack
return self.stack[-1]
def getMin(self) -> int:
# Return the top element of the min stack
return self.min_stack[-1]
4. JavaScript Try on Compiler
class MinStack {
constructor() {
// Initialize the main stack and the min stack
this.stack = [];
this.minStack = [];
}
push(x) {
// Add x to the main stack
this.stack.push(x);
// Add x to the min stack if it's empty or x <= top of minStack
if (this.minStack.length === 0 || x <= this.minStack[this.minStack.length - 1]) {
this.minStack.push(x);
}
}
pop() {
// If the top of the main stack equals the top of the min stack, remove it from the min stack
if (this.stack[this.stack.length - 1] === this.minStack[this.minStack.length - 1]) {
this.minStack.pop();
}
// Remove the top element from the main stack
this.stack.pop();
}
top() {
// Return the top element of the main stack
return this.stack[this.stack.length - 1];
}
getMin() {
// Return the top element of the min stack
return this.minStack[this.minStack.length - 1];
}
}Time Complexity: O(1)
push(x): Time Complexity: O(1)
Adding an element to the mainStack is O(1).
Comparing the element with the top of minStack and potentially adding it is also O(1).
pop(): Time Complexity: O(1)
Removing the top element from mainStack is O(1).
Checking and removing the top of minStack (if necessary) is O(1).
top(): Time Complexity: O(1)
Retrieving the top element from mainStack is O(1).
getMin(): Time Complexity: O(1)
Retrieving the top element from minStack is O(1).
The total time complexity is: O(1)+O(1)+O(1)+O(1) = O(1)
Space Complexity: O(n)
Auxiliary Space Complexity refers to the extra space required by an algorithm other than the input space.
mainStack: The mainStack stores all elements, so its space usage is proportional to the number of elements pushed: O(n).
minStack:
The minStack only stores elements when they are the minimum (or equal to the minimum) at the time of insertion. In the worst case (if all elements are distinct and in decreasing order), every element will also be added to minStack. Thus, its space complexity is also O(n).
Best case: If all elements are in increasing order, only one element (the first minimum) is stored in minStack.
The total Auxiliary space complexity is O(n).
Total Space Complexity
We use constant space to take input i.e. O(1)
Auxiliary space: O(n)
Total space complexity is: O(1) + O(n) = O(n)