Min Stack
Program for Implementing Min Stack Problem
Design a Min Stack class that efficiently supports the following operations, ensuring each runs in O(1) time complexity:
- MinStack()
- void push(int val)
- void pop()
- int top()
- int getMin()
Implementation should maintain an auxiliary structure to keep track of the minimum values to ensure all operations run efficiently.
void push(int val): Adds the element val to the top of the stack. Additionally, it keeps track of the current minimum value after this operation.
void pop(): Removes the topmost element from the stack. If the removed element was the minimum, the stack should update the minimum accordingly.
int top(): Returns the value of the element at the top of the stack without removing it.
int getMin(): Retrieves the smallest element in the stack at the current state. This operation should be constant time, regardless of the stack size.
Output: [null,null,null,null,0,null,2,1]
Explanation:
MinStack minStack = new MinStack();
minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.getMin(); // return 0
minStack.pop();
minStack.top(); // return 2
minStack.getMin(); // return 1
Constraints:
- -2^31 <= val <= 2^31 – 1.
- pop, top and getMin will always be called on non-empty stacks.
Program for Implementing Min Stack Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(1) time for each function call and O(n) space, where n is the maximum number of elements present in the stack.
Hints for solving problems
Hint 1 :
A brute force solution would be to continuously remove valid brackets until no more can be removed. If the remaining string is empty, return true; otherwise, return false. This would result in an O(n^2) solution. Can we think of a better approach? Perhaps a data structure could help.A basic approach would involve checking the minimum element in the stack each time the getMin() function is called. However, this approach would take O(n) time. Can you think of a more efficient solution, possibly using O(n) extra space to store additional information?
Hint 2 :
We can use a stack to store the elements, but how can we keep track of the minimum element at any given point? Consider using a prefix strategy to keep track of the minimum value.
Hint 3 :
Use a second stack to store the minimum value at each step. When removing elements from the main stack, also remove the corresponding value from this auxiliary stack. While pushing elements, compare the current value with the top of the auxiliary stack and store the smaller value in the auxiliary stack. This ensures the auxiliary stack always holds the minimum value at the current state.
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Two Stacks Method
- One Stack Method
1. Brute Force Method
Use a regular stack for storing elements and iterate through the stack whenever the minimum value is needed, resulting in O(n) time complexity for getMin().
- Time complexity: O(n) for getMin() and O(1) for other operations.
- Space complexity: O(n) for getMin() and O(1) for other operations.
Code
class MinStack {
public:
stack<int> stk;
MinStack() {
}
void push(int val) {
stk.push(val);
}
void pop() {
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
stack tmp;
int mini = stk.top();
while (stk.size()) {
mini = min(mini, stk.top());
tmp.push(stk.top());
stk.pop();
}
while (tmp.size()) {
stk.push(tmp.top());
tmp.pop();
}
return mini;
}
};
class MinStack {
private Stack<integer> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
stack.push(val);
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
Stack tmp = new Stack<>();
int mini = stack.peek();
while (!stack.isEmpty()) {
mini = Math.min(mini, stack.peek());
tmp.push(stack.pop());
}
while (!tmp.isEmpty()) {
stack.push(tmp.pop());
}
return mini;
}
}
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
self.stack.append(val)
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
tmp = []
mini = self.stack[-1]
while len(self.stack):
mini = min(mini, self.stack[-1])
tmp.append(self.stack.pop())
while len(tmp):
self.stack.append(tmp.pop())
return mini
class MinStack {
constructor() {
this.stack = [];
}
/**
* @param {number} val
* @return {void}
*/
push(val) {
this.stack.push(val);
}
/**
* @return {void}
*/
pop() {
this.stack.pop();
}
/**
* @return {number}
*/
top() {
return this.stack[this.stack.length - 1];
}
/**
* @return {number}
*/
getMin() {
const tmp = [];
let mini = this.stack[this.stack.length - 1];
while (this.stack.length > 0) {
mini = Math.min(mini, this.stack[this.stack.length - 1]);
tmp.push(this.stack.pop());
}
while (tmp.length > 0) {
this.stack.push(tmp.pop());
}
return mini;
}
}
2. Two Stacks Method
Use one stack to store all elements and another stack to keep track of the current minimum values, ensuring O(1) time complexity for getMin().
- Time complexity: O(1) for all operations.
- Space complexity: O(n)
Code
class MinStack {
private:
std::stack<int> stack;
std::stack<int> minStack;
public:
MinStack() {}
void push(int val) {
stack.push(val);
val = std::min(val, minStack.empty() ? val : minStack.top());
minStack.push(val);
}
void pop() {
stack.pop();
minStack.pop();
}
int top() {
return stack.top();
}
int getMin() {
return minStack.top();
}
};
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (stack.isEmpty()) return;
int top = stack.pop();
if (top == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
val = min(val, self.minStack[-1] if self.minStack else val)
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
/**
* @param {number} val
* @return {void}
*/
push(val) {
this.stack.push(val);
val = Math.min(
val,
this.minStack.length === 0
? val
: this.minStack[this.minStack.length - 1],
);
this.minStack.push(val);
}
/**
* @return {void}
*/
pop() {
this.stack.pop();
this.minStack.pop();
}
/**
* @return {number}
*/
top() {
return this.stack[this.stack.length - 1];
}
/**
* @return {number}
*/
getMin() {
return this.minStack[this.minStack.length - 1];
}
}
3. One Stack Method
Store both the value and the minimum value at each step in a single stack using a tuple, maintaining O(1) time complexity for all operations.
- Time complexity: O(1) for all operations.
- Space complexity: O(n)
Code
class MinStack {
private:
long min;
std::stack<long> stack;
public:
MinStack() {
}
void push(int val) {
if (stack.empty()) {
stack.push(0);
min = val;
} else {
stack.push(val - min);
if (val < min) min = val;
}
}
void pop() {
if (stack.empty()) return;
long pop = stack.top();
stack.pop();
if (pop < 0) min = min - pop; } int top() { long top = stack.top(); return (top > 0) ? (top + min) : (int)min;
}
int getMin() {
return (int)min;
}
};
public class MinStack {
long min;
Stack<Long> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0L);
min = x;
} else {
stack.push(x - min);
if (x < min) min = x;
}
}
public void pop() {
if (stack.isEmpty()) return;
long pop = stack.pop();
if (pop < 0) min = min - pop; } public int top() { long top = stack.peek(); if (top > 0) {
return (int) (top + min);
} else {
return (int) min;
}
}
public int getMin() {
return (int) min;
}
}
class MinStack:
def __init__(self):
self.min = float('inf')
self.stack = []
def push(self, x: int) -> None:
if not self.stack:
self.stack.append(0)
self.min = x
else:
self.stack.append(x - self.min)
if x < self.min:
self.min = x
def pop(self) -> None:
if not self.stack:
return
pop = self.stack.pop()
if pop < 0:
self.min = self.min - pop
def top(self) -> int:
top = self.stack[-1]
if top > 0:
return top + self.min
else:
return self.min
def getMin(self) -> int:
return self.min
class MinStack {
constructor() {
this.min = Infinity;
this.stack = [];
}
/**
* @param {number} val
* @return {void}
*/
push(val) {
if (this.stack.length === 0) {
this.stack.push(0);
this.min = val;
} else {
this.stack.push(val - this.min);
if (val < this.min) this.min = val;
}
}
/**
* @return {void}
*/
pop() {
if (this.stack.length === 0) return;
const pop = this.stack.pop();
if (pop < 0) this.min -= pop;
}
/**
* @return {number}
*/
top() {
const top = this.stack[this.stack.length - 1];
return top > 0 ? top + this.min : this.min;
}
/**
* @return {number}
*/
getMin() {
return this.min;
}
}
More Articles
155. Min Stack Leetcode Solution
Min Stack Leetcode Problem :
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.
Min Stack Leetcode Solution :
Constraints :
- -2^31 <= val <= 2^31 – 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.
Intuition :
The MinStack class is designed to maintain a stack of elements while also keeping track of the minimum element in the stack.
Approach :
1. The MinStack class uses a single stack, stk, to store pairs of elements and the minimum values encountered so far.
2: When an element is pushed onto the stack, the current minimum value is calculated by comparing the new element with the minimum value stored on top of the stack. The pair (element, current minimum) is then pushed onto the stack.
3: When an element is popped from the stack, it effectively removes the top pair, effectively reverting to the previous state.
4: The top function returns the first element of the top pair on the stack, and the getMin function returns the second element of the top pair, which represents the current minimum value.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class MinStack {
public:
typedef struct node{
int v;
int minUntilNow;
node* next;
}node;
MinStack() : topN(nullptr){
}
void push(int val) {
node* n = new node;
n->v = n->minUntilNow = val;
n->next = nullptr;
if(topN == nullptr){
topN = n;
}
else{
n->minUntilNow = min(n->v,topN->minUntilNow);
n->next = topN;
topN = n;
}
}
void pop() {
topN = topN->next;
}
int top() {
return topN->v;
}
int getMin() {
return topN->minUntilNow;
}
private:
node* topN;
};
class MinStack {
LinkedList< TplusMin> stack;
private class TplusMin {
int val;
int min;
public TplusMin(int val, int min) {
this.val = val;
this.min = min;
}
}
public MinStack() {
stack = new LinkedList<>();
}
public void push(int val) {
int newMin;
if (stack.size() == 0){
newMin = val;
}
else {
int currentMin = stack.getFirst().min;
newMin = val < currentMin ? val : currentMin;
}
stack.addFirst(new TplusMin(val, newMin));
}
public void pop() {
stack.removeFirst();
}
public int top() {
return stack.peekFirst().val;
}
public int getMin() {
return stack.peekFirst().min;
}
}
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
if self.minStack:
val = min(self.minStack[-1],val)
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment