Min Stack Problem
Difficulty: Medium, Asked-in: Adobe, Amazon, LinkedIn, Paytm, VMware.
Key takeaway: An excellent problem to learn data structure design.
Let’s understand the problem
Design and implement a stack that supports push, pop, top, and retrieving the minimum element in constant time. In other words, our goal is to implement the MinStack class, which supports the following methods with O(1) time complexity.
- void push(int x): Insert element x onto the stack.
- void pop(): Remove the top element from the stack.
- int top(): Retrieve the top element.
- int getMin(): Retrieve the minimum element in the stack.
Note: The methods pop, top, and getMin will always be called on non-empty stacks.
Before solving this problem, if you want to learn about the design and implementation of stack operations, you can explore this blog: Introduction to the Stack Data Structure.
MinStack implementation using two stacks
Here we have one critical task: We need to track the current minimum element during push and pop operations so that we can access the minimum in O(1) time. So, how can we achieve this? Let's think!
If we observe, we need to know the history of previous minimum values to track the current minimum. For example, if we push a new element x that is less than the current minimum, then element x will become our new current minimum. Similarly, if we pop the current minimum element, we need to update the current minimum with the previous minimum which can be found below the stack (requiring iteration over the stack to find it).
One idea would be to use two stacks to implement the MinStack: One stack to store elements (mainStack) and another stack (auxStack) to store the minimum elements at each stage. Our goal is to update the minimum element in auxStack when pushing and popping elements from the mainStack.
Push operation: We push the value into the mainStack. Now, we check if auxStack is empty or if the new value is less than or equal to the top value of auxStack. If either condition is true, we push the new value onto auxStack. This ensures that auxStack always contains the minimum value at the top.
Pop operation: We remove the top value from the mainStack and check if the popped value is equal to the top value of auxStack. If they are equal, it means we are removing the minimum value from the mainStack. So, we also remove the top value from auxStack.
Get minimum operation: We simply return the top value of auxStack, which is the current minimum value.
Top operation: We simply return the top value of the mainStack.
Implementation code C++
class MinStack {
private:
stack<int> mainStack;
stack<int> auxStack;
public:
void push(int value) {
mainStack.push(value);
if (auxStack.empty() || value <= auxStack.top()) {
auxStack.push(value);
}
}
void pop() {
int topValue = mainStack.pop();
if (topValue == auxStack.top()) {
auxStack.pop();
}
}
int getMinimum() {
return auxStack.top();
}
int top() {
return mainStack.top();
}
};Implementation code Java
class MinStack {
private Stack<Integer> mainStack;
private Stack<Integer> auxStack;
public MinStack() {
mainStack = new Stack<>();
auxStack = new Stack<>();
}
public void push(int value) {
mainStack.push(value);
if (auxStack.isEmpty() || value <= auxStack.peek()) {
auxStack.push(value);
}
}
public void pop() {
int topValue = mainStack.pop();
if (topValue == auxStack.peek()) {
auxStack.pop();
}
}
public int getMinimum() {
return auxStack.peek();
}
public int top() {
return mainStack.peek();
}
}Implementation code Python
class MinStack:
def __init__(self):
self.mainStack = []
self.auxStack = []
def push(self, value):
self.mainStack.append(value)
if len(self.auxStack) == 0 or value <= self.auxStack[-1]:
self.auxStack.append(value)
def pop(self):
topValue = self.mainStack.pop()
if topValue == self.auxStack[-1]:
self.auxStack.pop()
def getMinimum(self):
return self.auxStack[-1]
def top(self):
return self.mainStack[-1]Time and space complexity analysis
In this algorithm, each operation will take O(1) time. We use an extra stack to store the record of the minimum element at each stage. So, we will need O(n) space in the worst case. The critical question is: What would be the best and worst-case scenario? Explore and think!
Using one stack and pairs to store the value and current minimum
Solution idea
During every push and pop operation, we need to track the minimum up to that point. The critical question is: Can we solve this problem using a single stack? One idea would be to use a pair to store two elements together: The first element in the pair stores the actual value, and the second element stores the minimum element encountered so far.
Push operation
During the first push operation, we push the value into the stack and store it as the minimum element itself in the pair. This is because there are no previous elements to compare it with, so the minimum element encountered so far is simply the value itself.
In subsequent push operations, we check if the minimum stored in the top pair of the stack (the second element in the pair) is less than the new value. If it is, it means the minimum element encountered so far remains the same, so we push the new value along with the same minimum value as a pair.
Otherwise, if the new value is the new minimum, we push the new value and the updated minimum as a pair. This ensures that we always have the minimum element stored in the second element of the top pair.
Pop operation: We simply remove the top element from the stack.
Top operation: We return the first element of the pair at the top of the stack.
Get minimum operation: The second element of the pair at the top of the stack will store the current minimum of the stack. So we return this value.
Implementation code C++
class MinStack {
private:
stack<pair<int, int>> s;
public:
void push(int x) {
int min;
if (s.empty()) {
min = x;
} else {
min = min(s.top().second, x);
}
s.push({x, min});
}
void pop() {
s.pop();
}
int top() {
return s.top().first;
}
int getMin() {
return s.top().second;
}
};Implementation code Java
class MinStack {
private Stack<Pair> stack;
private class Pair {
public int value;
public int minimum;
public Pair(int value, int minimum) {
this.value = value;
this.minimum = minimum;
}
}
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
int min;
if (stack.isEmpty()) {
min = x;
} else {
min = Math.min(stack.peek().minimum, x);
}
stack.push(new Pair(x, min));
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek().value;
}
public int getMin() {
return stack.peek().minimum;
}
}Implementation code Python
class MinStack:
class Pair:
def __init__(self, value, minimum):
self.value = value
self.minimum = minimum
def __init__(self):
self.stack = []
def push(self, x):
if not self.stack:
minimum = x
else:
minimum = min(self.stack[-1].minimum, x)
pair = self.Pair(x, minimum)
self.stack.append(pair)
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1].value
def getMin(self):
return self.stack[-1].minimumTime and space complexity analysis
In the above approach, each operation has a time complexity of O(1). We use a single stack but store an additional detail for each element to track the minimum element. So, the space complexity remains O(n).
Implementation using linked list implementation of the stack
This idea is similar to the above approach, but instead, we use a linked list implementation of the stack. In this approach, we maintain a separate min variable in each node to store the minimum value up to that node. We update the min value at each node accordingly when we push or pop elements.
Solution steps
We define MinStack class which contains a private inner class called Node (represents a node in the stack). Each node stores three pieces of information: the value of the element, the minimum value up to that node, and the next pointer. We also define a private head variable, which points to the topmost node in the stack.
- Push operation: If the stack is empty (head == NULL), we create a new node with x as both the value and the minimum. Otherwise, we create a new node with x as the value and the min (x, head->min) as the minimum. We update this newly created node as the new head.
- Pop operation: We remove the top element by updating the head to point to the next node.
- Top operation: We return the value of the top element in the stack (head->val).
- Get minimum operation: We return the value stored in the min variable of the top node (head->min).
Implementation code C++
class MinStack {
private:
struct Node {
int val;
int min;
Node* next;
Node(int value, int minimum, Node* nxt){
val = value;
min = minimum;
next = nxt;
}
};
Node* head;
public:
MinStack(){
head = NULL;
}
void push(int x) {
if (head == NULL)
head = new Node(x, x, NULL);
else
head = new Node(x, min(x, head->min), head);
}
void pop() {
Node* temp = head;
head = head->next;
delete temp;
}
int top() {
return head->val;
}
int getMin() {
return head->min;
}
};Implementation code Java
class MinStack {
private class Node {
int val;
int min;
Node next;
Node(int value, int minimum, Node nxt) {
val = value;
min = minimum;
next = nxt;
}
}
private Node head;
public MinStack() {
head = null;
}
public void push(int x) {
if (head == null)
head = new Node(x, x, null);
else
head = new Node(x, Math.min(x, head.min), head);
}
public void pop() {
Node temp = head;
head = head.next;
temp.next = null; // Release the reference to the popped node for garbage collection
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
}Implementation code Python
class MinStack:
class Node:
def __init__(self, value, minimum, nxt):
self.val = value
self.min = minimum
self.next = nxt
def __init__(self):
self.head = None
def push(self, x):
if self.head is None:
self.head = self.Node(x, x, None)
else:
self.head = self.Node(x, min(x, self.head.min), self.head)
def pop(self):
temp = self.head
self.head = self.head.next
temp.next = None
def top(self):
return self.head.val
def getMin(self):
return self.head.minTime and space complexity analysis
The time complexity of each operation is O(1). We store an additional detail within each node to track the minimum element, so the space complexity remains O(n).
Another implementation using stack
This idea is similar to the two-stack solution. There is one difference: We use the same stack to store both elements and track the history of minimum elements.
Whenever a new minimum element x arrives, we push the current minimum (stored in the variable "min"), update the minimum with x, and push x to the stack. So we store every instance of the minimum and the previous minimum together. During the pop operation, when we remove the current minimum, the previous minimum can be retrieved easily by another pop operation.
Here is another perspective to understand the idea:
- When the current minimum value changes after pushing the new value x, we also push the old minimum value along with x. Otherwise, we just push x.
- If the pop operation results in a change of the current minimum value, we pop twice and update the current minimum value to the last minimum value. Otherwise, we pop once.
Let's understand this with an example. Suppose we push 3, 2, 4 and 1 into the stack.
- Push 3: min = 3, Stack = [3].
- Push 2: 2 is the new minimum. So we push the current minimum 3, update min = 2, and push 2. Stack = [3, 3, 2].
- Push 4: min = 2, Stack = [3, 3, 2, 4].
- Push 1: 1 is the new minimum. So we push the current minimum 2, update min = 1, and push 1. Stack = [3, 3, 2, 4, 2, 1].
Now we pop the top three elements from the stack.
- 1st pop: Current minimum 1 is at the top. So we pop 1, set the current minimum with the stack top (which is the previous minimum value 2), and pop 2. Stack = [3, 3, 2, 4].
- 2nd pop: We simply pop 4. Stack = [3, 3, 2]
- 3rd pop: Current minimum 2 is at the top. So we pop 2, set the current minimum with the stack top (which is the previous minimum value 3), and pop 3. Stack = [3].
Solution steps
Push operation: First, we check if x is less than or equal to the current minimum value (min). If it is, x becomes the new minimum value. We push the current minimum value (min) onto the stack before updating min to x. This preserves the previous minimum value, which can be restored later when we pop the minimum element. After handling the minimum value, we push the new element x onto the stack as usual.
Pop operation: First, we remove the top element from the stack and check if the popped value is equal to the current minimum value (min). If it is, we need to update the minimum value. So, we pop the top element of the stack again (corresponding to the previous minimum value) and update the min with this value.
Top operation: We simply return the top element of the stack.
getMin operation: We return the value stored in the min variable.
Implementation code C++
class MinStack {
private:
int min;
stack<int> s;
public:
MinStack() {
min = INT_MAX;;
}
void push(int x) {
if (x <= min) {
s.push(min);
min = x;
}
s.push(x);
}
void pop() {
if (s.top() == min) {
s.pop();
min = s.top();
}
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return min;
}
};Implementation code Java
class MinStack {
private int min;
private Stack<Integer> stack;
public MinStack() {
min = Integer.MAX_VALUE;
stack = new Stack<>();
}
public void push(int x) {
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
if (stack.peek() == min) {
stack.pop();
min = stack.peek();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}Implementation code Python
class MinStack:
def __init__(self):
self.min = float('inf')
self.stack = []
def push(self, x):
if x <= self.min:
self.stack.append(self.min)
self.min = x
self.stack.append(x)
def pop(self):
if self.stack[-1] == self.min:
self.stack.pop()
self.min = self.stack[-1]
self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.minTime and space complexity analysis
Here, each operation will take O(1) time. We are using just a single stack, but the size of this stack is larger compared to the previous approach. The idea is simple: we also push minimum elements in the same stack. So, in the worst case, the extra space used for the stack will be O(n). Think!
Critical ideas to think!
- Can we consider solving this problem using a different approach?
- What would be the space complexity of the last approach in the best and worst cases?
- After performing n push operations followed by n pop operations, how many standard stack operations will be required in the last approach?
- Suppose we also need to track the current maximum in O(1). How can we modify the above approaches?
Suggested coding problems to explore
- Given a stack, sort its values in ascending order.
- Given a stack, reverse the order of its elements.
- Design a data structure that supports inserting, delete, search and get random in constant time.
- Design a special stack such that the maximum element can be found in O(1) time and O(1) extra space.
- Design a Data structure which supports insertion and the first non-repeating element in O(1) time. Operations that are supported by the data structure:
- Implement stack using queue
- Implement queue using stack
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!