As per the LeetCode MinStack problem, we have to design a stack that supports push, pop, top, and retrieving the minimum element in constant time, with each of these functions performing the following tasks:
-
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.
For example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // Returns -3
minStack.pop();
minStack.top(); // Returns 0
minStack.getMin(); // Returns -2
Problem Statement:
The question asks us to implement a stack, with the typical features of LIFO ( Last In First Out ) like inserting a value in the stack (push), deleting the topmost entry (pop), and fetching the topmost value (top). All three of them can be easily be worked out using a simple C++ STL Stack.
But the question is not that simple, there is a twist. We also need to retrieve the least value present in the entire stack. If instead, we had an array, this can be achieved by applying search techniques. What do we do now? Do not forget that we have only access to the topmost element of our stack.
MinStack Solution Approach:
We maintain a variable called minInStack which stores the minimum value amongst all the entries of the stack. We will intialise it with INT_MAX, and then, whenever we push a new element in our stack, we check that if it is smaller than the value already stored in minInStack.
If it turns out that the new value to be inserted is indeed smaller, push both the value in minInStack and the new value to be inserted into the stack, and update minInStack to this new value which is pushed. Otherwise , just push the new element.
When deleting the top element , we check if the topmost value is the same as that stored in minInStack variable, if it is the same, it means that the least value present in the entire stack is leaving our stack. As we have already stored the second-best candidate for this value in the stack before pushing this value, we will update the minInStack variable with this value and pop out both the values.
Retrieving the top element is trivial, just the basic operation of the STL stack.
And for getMin(), we return the value of the minInStack variable.
MinStack C++ Solution:
Following is the solution to the above problem in C++ programming language. Once you understand this you can easily implement this in various other languages.
class MinStack {
public:
stack<int>st;
int minInStack = INT_MAX;
void push(int x) {
if(x <= minInStack){
st.push(minInStack);
minInStack = x;
}
st.push(x);
}
void pop() {
int tmp = st.top();
st.pop();
if(tmp == minInStack){
minInStack = st.top();
st.pop();
}
}
int top() {
return st.top();
}
int getMin() {
return minInStack;
}
};
If you have any doubts, feel free to ask anything.
You may also like:
