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;
}
}
