The stack is a data structure that operates in LIFO order. This means last in, first out. Let’s understand through an example: In a school bus, the last person to enter will be the first to exit. In this article, we will discuss the different solutions to the question Min Stack problem from Leetcode.
What is the Min Stack problem?
In the Min Stack problem, you are required to perform various operations like push, pop, topmost element, and minimum element from the stack. You must perform all the operations in constant time, O(1).
This includes tasks like:
- Add elements into the stack.
- Remove or pop elements from the stack.
- Print the topmost element from the stack.
- Or to get the minimum element from the stack.
Let’s consider an example where you begin with an empty stack and perform the following operations: [“push, 1”, ”push, 2”, ”pop”, “push, 3”, “top”, “min”].
- After the initial push 1, the stack becomes
- After the next push 2, the stack becomes
- At the next pop remove the top element from the stack.
- Now push 3 in the stack
- Print the top element from the stack in this case top element is 3.
- Print minimum from the stack. The minimum is 1 so it prints 1.
Using Two-Stack Approach
This approach uses two stacks: one takes care of the minimum element till now, while the other is to store all the elements. Whenever we have to print the minimum element, we print that from the min_stack. If we have to print the topmost element of the stack, we use the regular stack.
Let’s examine each step with the same example [“push, 1”, ”push, 2”, ”pop”, “push, 3”, “top”, “min”].
- Create two stacks min_stack and main_stack.
- If the operation is ‘push,’ then push the value into the main_stack and check whether the min_stack is empty or if the top value of the min_stack is greater than the current value. If it is, push the value into the min_stack; otherwise, do not.
- If the operation is “pop”, then check if the min_stack top value is the same as of main_stack if so, remove an element from both the stacks, otherwise remove only from main_stack.
- If the operation is ‘top,’ then print the topmost element from the main_stack.
- If the operation is ‘Min,’ then print the topmost element from the min_stack.
As in this approach, we are not using any loop in any of the operations so, the time complexity is O(1) which is required. As we are using two stacks to solve the problem, the space complexity is O(2*n), where n represents the number of values we need to add.
Using Only One Stack to Solve Min Stack
As in the above approach, we are using two stacks which increases our space complexity. We can solve the Min Stack problem with one stack also. Let’s examine each step:
- Create an empty stack and a variable that stores the minimum value at each point.
- Now, if it is the “push” operation, check if the stack is empty or the minimum value is less than the current value. If it is, push the value to the stack.
- If not then push (2*current_value)-min and update the minimum value to the current value. We are doing this because if we take out this element in the operation ‘pop’ we can get the previous min value.
- If it is the ‘pop’ operation, check whether the topmost element is greater than the minimum value. If it is, then pop directly otherwise update the minimum value to ((2*minimum_value) – topmost value). Pop the element.
- If it is the ‘top’ operation then check if the topmost element is greater than the minimum value if it is then print the topmost element otherwise print the minimum value.
- If it is the ‘min’ operation then print the minimum value.
C++ Code
Check the C++ solution below:
#include <bits/stdc++.h>
using namespace std;
// creating a stack.
stack<long long int>s;
// creating a variable that stores minimum value
long long int mn;
// push function
void push(long long int value){
if (s.size()==0) {
s.push(value);
mn = value;
} else if(value >= mn) {
s.push(value);
} else if (value < mn) {
s.push((2 * value)-mn);
mn = value;
}
}
// pop function
void pop(){
if(s.top()>=mn){
s.pop();
}else if(s.top()<mn){
mn = (2*mn)-s.top();
s.pop();
}
}
long long int top(){
if(!s.size())return -1;
else if(s.top()>=mn)return s.top();
else return mn;
}
long long int getmin(){
if(s.size()) return mn;
return 0;
}
int main(){
// call for push operation with value 1
push(1);
// call for push operation with value 2
push(2);
// call for pop operation
pop();
// call for push operation with value 3
push(3);
// call for top opertion
int x = top();
// printing topmost element
cout<<x<<endl; // output will be 3
// call for minimum opertion
int y = getmin();
// printing the minimum value
cout<<y<<endl; // output will be 1
return 0;
}Java Code
Here is the Java code to solve Min Stack problem using one stack only:
import java.util.Stack;
public class Main {
static Stack<Long> s = new Stack<>();
static long mn;
static void push(long value) {
if (s.size() == 0) {
s.push(value);
mn = value;
} else if (value >= mn) {
s.push(value);
} else if (value < mn) {
s.push((2 * value) - mn);
mn = value;
}
}
static void pop() {
if (s.peek() >= mn) {
s.pop();
} else if (s.peek() < mn) {
mn = (2 * mn) - s.peek();
s.pop();
}
}
static long top() {
if (s.size() == 0) return -1;
else if (s.peek() >= mn) return s.peek();
else return mn;
}
static long getmin() {
if (s.size() != 0) return mn;
return 0;
}
public static void main(String[] args) {
// call for push operation with value 1
push(1);
// call for push operation with value 2
push(2);
// call for pop operation
pop();
// call for push operation with value 3
push(3);
// call for top operation
long x = top();
// printing topmost element
System.out.println(x); // output will be 3
// call for minimum operation
long y = getmin();
// printing the minimum value
System.out.println(y); // output will be 1
}
}Python Code
Below is the Python code as well:
s = []
mn = 0
def push(value):
global mn
if len(s) == 0:
s.append(value)
mn = value
elif value >= mn:
s.append(value)
elif value < mn:
s.append((2 * value) - mn)
mn = value
def pop():
global mn
if s[-1] >= mn:
s.pop()
elif s[-1] < mn:
mn = (2 * mn) - s[-1]
s.pop()
def top():
if len(s) == 0:
return -1
elif s[-1] >= mn:
return s[-1]
else:
return mn
def getmin():
if len(s) != 0:
return mn
return 0
# call for push operation with value one.
push(1)
# call for push operation with value two.
push(2)
# call for pop operation
pop()
# call for push operation with value three.
push(3)
# call for top operation
x = top()
# printing topmost element
print(x) # output will be 3
# call for minimum operation
y = getmin()
# printing the minimum value
print(y) # output will be 1Output:
3
1As we have seen, we are using just one stack to perform any operation, so the space complexity will not be O(n), and the time complexity remains O(1), as mentioned above.
Conclusion
Min Stack problem from leetcode is often asked in many Data Structures coding interviews. We can also solve this problem using a Linked List instead of using a stack because a stack is composed of a linked list. Trying to solve this question using a linked list and finding its time and space complexity will yield the same results as in the one-stack approach.
