Let's assume the stack which we will be working on is this :
6 , minvalue=2
2 , minvalue=2
5 , minvalue=3
3 , minvalue=3
9 , minvalue=7
7 , minvalue=7
8 , minvalue=8
In the above representation the stack is only built by left value's the right value's [minvalue] is written only for illustration purpose which will be stored in one variable.
The actual problem is when the value which is the minimum value gets removed: At that point how can we know what is the next minimum element without iterating over the stack.
Like for example in our stack when 6 gets popped we know that, this is not the minimum element because the minimum element is 2, so we can safely remove this without updating our min value.
But when we pop 2, we can see that the minimum value is 2 right now and if this gets popped out then we need to update the minimum value to 3.
Point1:
Now if you observe carefully we need to generate minvalue=3 from this particular state [2 , minvalue=2].
Or if you go deeper in the stack we need to generate minvalue=7 from this particular state [3 , minvalue=3]
or if you go deeper still in the stack then we need to generate minvalue=8 from this particular state [7 , minvalue=7]
Did you notice something in common in all of the above three cases? The value which we need to generate depends upon two variable which are both equal. Correct.
Why is this happening because when we push some element smaller then the current minvalue, then we basically push that element in the stack and updated the same number in minvalue also.
Point2:
So we are basically storing duplicate of the same number once in stack and once in minvalue variable.
We need to focus on avoiding this duplication and store something useful data in the stack or the minvalue to generate the previous minimum as shown in CASES above.
Let's focus on what should we store in stack when the value to store in push is less than the minimum value.
Let's name this variable y, so now our stack will look something like this:
6 , minvalue=2
y1 , minvalue=2
5 , minvalue=3
y2 , minvalue=3
9 , minvalue=7
y3 , minvalue=7
8 , minvalue=8
I have renamed them as y1,y2,y3 to avoid confusion that all of them will have same value.
Point3:
Now let's try to find some constraint's over y1, y2 and y3.
Do you remember when exactly we need to update the minvalue while doing pop(), only when we have popped the element which is equal to the minvalue.
If we pop something greater than the minvalue then we don't have to update minvalue.
So to trigger the update of minvalue, y1,y2&y3 should be smaller than there corresponding minvalue. [We are avoiding equality to avoid duplicate[Point2]]
so the constrain is [ y < minValue ].
Now let's come back to populate y, we need to generate some value and put y at the time of push, remember.
Let's take the value which is coming for push to be x which is less that the prevMinvalue, and the value which we will actually push in stack to be y.
So one thing is obvious that the newMinValue=x, and y < newMinvalue.
Now we need to calculate y(remember y can be any number which is less than newMinValue(x) so we need to find some number which can fulfil our constraint) with the help of prevMinvalue and x(newMinvalue).
Let's do the math:
x < prevMinvalue [Given]
x - prevMinvalue < 0
x - prevMinValue + x < 0 + x [Add x on both side]
2*x - prevMinValue < x
this is the y which we were looking for less than x(newMinValue).
y = 2*x - prevMinValue. 'or' y = 2*newMinValue - prevMinValue 'or' y = 2*curMinValue - prevMinValue [taking curMinValue=newMinValue].
So at the time of pushing x if it is less than prevMinvalue then we push y[2*x-prevMinValue] and update newMinValue = x .
And at the time of pop if the stack contains something less than the minValue then that's our trigger to update the minValue.
We have to calculate prevMinValue from the curMinValue and y.
y = 2*curMinValue - prevMinValue [Proved]
prevMinValue = 2*curMinvalue - y .
2*curMinValue - y is the number which we need to update now to the prevMinValue.
Code for the same logic is shared below with O(1) time and O(1) space complexity.
// C++ program to implement a stack that supports
// getMinimum() in O(1) time and O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
// A user defined stack that supports getMin() in
// addition to push() and pop()
struct MyStack
{
stack<int> s;
int minEle;
// Prints minimum element of MyStack
void getMin()
{
if (s.empty())
cout << "Stack is empty\n";
// variable minEle stores the minimum element
// in the stack.
else
cout <<"Minimum Element in the stack is: "
<< minEle << "\n";
}
// Prints top element of MyStack
void peek()
{
if (s.empty())
{
cout << "Stack is empty ";
return;
}
int t = s.top(); // Top element.
cout << "Top Most Element is: ";
// If t < minEle means minEle stores
// value of t.
(t < minEle)? cout << minEle: cout << t;
}
// Remove the top element from MyStack
void pop()
{
if (s.empty())
{
cout << "Stack is empty\n";
return;
}
cout << "Top Most Element Removed: ";
int t = s.top();
s.pop();
// Minimum will change as the minimum element
// of the stack is being removed.
if (t < minEle)
{
cout << minEle << "\n";
minEle = 2*minEle - t;
}
else
cout << t << "\n";
}
// Removes top element from MyStack
void push(int x)
{
// Insert new number into the stack
if (s.empty())
{
minEle = x;
s.push(x);
cout << "Number Inserted: " << x << "\n";
return;
}
// If new number is less than minEle
if (x < minEle)
{
s.push(2*x - minEle);
minEle = x;
}
else
s.push(x);
cout << "Number Inserted: " << x << "\n";
}
};
// Driver Code
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.peek();
return 0;
}
