C++ solution using O(1) extra space simple math trick
One of the simple way to solve this problem is using an auxillary stack keeping track of all the minimum elements. \nHowever using simple math trick we can solv
One of the simple way to solve this problem is using an auxillary stack keeping track of all the minimum elements. \nHowever using simple math trick we can solve without using any auxillary stack.\nIdea :\n1. At any point let the current minimum be minn.\n2. Suppose we are pushing any element e , such that e>= minn. Then there is no need to update minn. Simply push the element in to the stack.\n3. If e < minn, we will push e and  we will also need to update minn. Let us do the update as minn=e. However there will be a problem.  Let us see what.\n4.  If now a pop operation is called since the minimum is now at the top of the stack we need to update minn to the previous minn. But since we are not using any auxillary stack how to retrive the previous min?\n5.  This can be acheived if in step 3 instead of pushing e into the stack we push **2\\*e-minn** instead.   Why?\n\tWe know, e<minn\n\t=> e-minn<0\n\t=> e-minn+e<e\n\t=>2\\*e-minn<e\n\tSo we can say the instead of pushing e in step 3 we are pushing a number even less than e. After doing this update minn=e. How will this help? \n\t**Note - Update is done after pushing 2\\*e-minn in the stack. It means the "minn" in "2\\*e-minn" is actually the minn before encountering e which thus the becomes the previous_min after updating.**\n6. Now if we perform a pop operation the top of the stack will have a number less than minn (As top_of_the_stack = 2\\*e-previous_minn and minn=e). So now we can easily say **previous_min = 2\\*minn- top_of_stack**. This is important as we are keeping track of previous min also but using any extra space. So now we can pop the element and update minn=previous_min;\nIts very simple to implement.\nCode :- \n```\n#define ll long long int \nclass MinStack {\npublic:\n    /** initialize your data structure here. */\n    vector<ll> s;\n    int minn;\n    MinStack() {\n        minn=INT_MAX;\n    }\n    \n    void push(int val) {\n        if(s.empty()){\n            s.push_back(val);\n            minn=val;\n        }\n        else if(val>=minn)\n            s.push_back(val);\n        else{\n            s.push_back(2LL*val-minn);//Insert a number even less then val\n            minn=val;\n        }\n    }\n    \n    void pop() {\n        auto it = s.end();\n        ll e = *(--it);\n        if(e<minn)\n        {\n            minn=2LL*minn-e;//Retrive the prev min\n            \n        }\n          s.erase(it);         \n    }\n    \n    int top() {\n        auto it = s.end();\n        ll e = *(--it);\n        if(e<minn) return minn;\n        return e;\n    }\n    \n    int getMin() {\n        return minn;\n    }\n};\n\n/**\n * Your MinStack object will be instantiated and called as such:\n * MinStack* obj = new MinStack();\n * obj->push(val);\n * obj->pop();\n * int param_3 = obj->top();\n * int param_4 = obj->getMin();\n */\n```
['Math', 'C']