Solution For Min Stack
Problem Statement:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- getMin() – Retrieve the minimum element in the stack.
Approach:
The key to solving this problem is to maintain a separate stack which only stores the minimum elements. The minimum element stack keeps track of the minimum element at any given point of time.
Algorithm:
We can implement the Min Stack using two stacks – a main stack and a minimum stack.
When an element is pushed onto the main stack, it is also compared to the element at the top of the minimum stack. If the minimum stack is empty or the element is smaller than or equal to the top of the minimum stack, the element is pushed onto the minimum stack.
When an element is popped from the main stack, it is also compared to the element at the top of the minimum stack. If the element is equal to the top of the minimum stack, that element is popped from the minimum stack as well.
To retrieve the minimum element in the stack, simply return the top element of the minimum stack.
To retrieve the top element of the stack, simply return the top element of the main stack.
Let’s look at the implementation in Python:
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
Time Complexity:
- The time complexity of push, pop, top, and getMin is O(1).
Space Complexity:
- The space complexity of Min Stack is O(n), where n is the total number of elements in the stack.
Conclusion:
In this article, we learned how to implement the Min Stack problem using two stacks. We also discussed the algorithm and the corresponding Python implementation.
Step by Step Implementation For Min Stack
class MinStack {
// Create a stack data structure
Stack stack;
// Create a variable to keep track of the minimum value
int min;
public MinStack() {
stack = new Stack();
}
public void push(int x) {
// If the stack is empty, set the min to the pushed value
if (stack.isEmpty()) {
min = x;
}
// If the pushed value is less than the current min, set the min to the pushed value
else if (x < min) {
min = x;
}
// Push the value onto the stack
stack.push(x);
}
public void pop() {
// If the stack is empty, do nothing
if (stack.isEmpty()) {
return;
}
// Get the top value on the stack
int top = stack.pop();
// If the top value is the same as the current min, pop the min value off the stack
if (top == min) {
min = stack.pop();
}
}
public int top() {
// If the stack is empty, return -1
if (stack.isEmpty()) {
return -1;
}
// Return the top value on the stack
return stack.peek();
}
public int getMin() {
// If the stack is empty, return -1
if (stack.isEmpty()) {
return -1;
}
// Return the current min value
return min;
}
} class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.min or x <= self.min[-1]:
self.min.append(x)
def pop(self) -> None:
if self.stack.pop() == self.min[-1]:
self.min.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min[-1]/**
* initialize your data structure here.
*/
var MinStack = function() {
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = Object.create(MinStack).createNew()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
// Add item to stack
stk.push(x);
// If min stack is empty or current item is less than top of min stack,
// push it onto the min stack
if (minStk.empty() || x <= minStk.top()) {
minStk.push(x);
}
}
void pop() {
// If stack is not empty
if (!stk.empty()) {
// Get top of both stacks
int topStk = stk.top();
int topMinStk = minStk.top();
// If top of min stack is equal to top of stack, pop from min stack
if (topMinStk == topStk) {
minStk.pop();
}
// Pop from stack
stk.pop();
}
}
int top() {
// If stack is empty, return -1
if (stk.empty()) {
return -1;
}
// Return top of stack
return stk.top();
}
int getMin() {
// If min stack is empty, return -1
if (minStk.empty()) {
return -1;
}
// Return top of min stack
return minStk.top();
}
private:
// Stack to store items
stack stk;
// Stack to store minimum values
stack minStk;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/ using System;
public class MinStack
{
private Stack s;
private int minEle;
public MinStack()
{
s = new Stack();
}
public void push(int x)
{
if (s.Count == 0)
{
minEle = x;
s.Push(x);
Console.WriteLine("Number Inserted: " + x);
return;
}
if (x < minEle)
{
s.Push(2*x - minEle);
minEle = x;
}
else
s.Push(x);
Console.WriteLine("Number Inserted: " + x);
}
public void pop()
{
if (s.Count == 0)
{
Console.WriteLine("Stack is Empty");
return;
}
Console.WriteLine("Top Most Element Removed: ");
int t = s.Pop();
if (t < minEle)
{
Console.WriteLine(minEle);
minEle = 2*minEle - t;
}
else
Console.WriteLine(t);
}
public int top()
{
if (s.Count == 0)
{
Console.WriteLine("Stack is Empty");
return -1;
}
int t = s.Peek();
if (t < minEle)
return minEle;
else
return t;
}
public int getMin()
{
if (s.Count == 0)
{
Console.WriteLine("Stack is Empty");
return -1;
}
else
return minEle;
}
}