Question: Design a min stack.
Min stack is stack with 3 operations,
1> push(x) push element x on to the stack
2> pop() pop element off the stack
3> min() get the current min of the stack
4> all operations must take O(1) time
|__5__| push 5
|__2__| push 2
|__5__|
|__4__| push 4
|__2__|
|__5__|
|__4__| min() = 2
|__2__|
|__5__|
|__2__| pop() = 4 min = 2
|__5__|
So by looking at this, first thinking might be to the following.
push(x){
stack.push(x)
if(x<min)
min = x
}
}
pop(){
x = stack.pop()
if(x == min){
min = search()
}
}
peek(){
return stack.peek()
}
min(){
return min
}
search(){
min = Number.MAX_VALUE
for(i=0;i<stack.length;i++)
if(stack[i]<min) min = stack[i]
return min
}
Here we're checking if the element being pushed, is it the less than the existing minimum value if it is then updating the min and push the element into the stack.
Whereas when we pop, if the element is the min value, then search for the next min value, but searching the next min takes O(n) linear time. We're aiming for O(1) constant min value.
The solution is to use two stacks, one which keeps actual elements, one which keeps min values, the idea is
1> Add element to the main stack, if the current element being pushed is less than the peek() of min stack, then add the push the new min value, or else push the existing min value to the min values stack.
2> when you pop(), pop both from main stack and min stack.
3> when min() is called, return peek() of min stack.
main stack min stack
|__5__| |__5__| push 5
|__2__| |__2__| push 2
|__5__| |__5__|
|__4__| |__2__| push 4 // here see that min stack peek() is 2
|__2__| |__2__|
|__5__| |__5__|
|__1__| |__1__| push 1 // min stack peek() changed to 1
|__4__| |__2__|
|__2__| |__2__|
|__5__| |__5__|
min(): 1
|__1__| |__1__| push 1 // min stack peek() changed to 1
|__4__| |__2__|
|__2__| |__2__|
|__5__| |__5__|
pop(): 1
|__4__| |__2__| pop // min peek() value changed to 2
|__2__| |__2__|
|__5__| |__5__|
min() : 2
|__4__| |__2__| pop // min peek() value changed to 2
|__2__| |__2__|
|__5__| |__5__|
and this pattern goes on
The other way of doing the same is
push(x){
stack.push(x)
if(minstack.size() == 0){
minstack.push(x)
}else{thi
int element = x
if(minstack.peek()< element){
minstack.push(minstack.peek())
}else{
minstack.push(element)
}
}
pop(){
minstack.pop()
return stack.pop()
}
peek(){
return stack.size()>0 ? stack.peek() : null
}
min(){
return minstack.size()>0 ? minstack.peek() : null
}
This ensures constant time push(),peek(),min(),pop() operation at the cost of extra o(n) space.
var MinStack = function() {
this.stack = [];
this.min = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
var min = this.getMin();
if (min !== undefined) {
this.min.push(Math.min(x, min));
} else {
this.min.push(x);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.stack.pop();
this.min.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
if (this.stack.length > 0) {
return this.stack[this.stack.length - 1];
}
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
if (this.min.length > 0) {
return this.min[this.min.length - 1];
}
};
Hope it helps :D
github: https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/Design/minStack.java
Top comments (0)