3 APPROACHES | Time & SPACE O(1)  | C++
APPROACH 1: TIME O(1) SPACE O(N)\nusing vector pair \n\n\nclass MinStack {\npublic:\n    vector<pair<int, int>> v;\n    void push(int val) \n    {\n        if (
APPROACH 1: TIME O(1) SPACE O(N)\nusing vector pair <val, minimum val til current element>\n\n```\nclass MinStack {\npublic:\n    vector<pair<int, int>> v;\n    void push(int val) \n    {\n        if (v.empty())  v.push_back({val, val}); \n        else  \n            v.push_back({val, min(val, v.back().second)}); //v.back() == v[v.size()-1]\n    }\n    void pop() { v.pop_back(); }\n    int top() { return v.back().first; }\n    int getMin() { return v.back().second; }\n};\n```\n\n#APPROACH 2: TIME O(1) SPACE O(N)\nusing 2 stack implementation.\n\nLogic: maintain minimum in mini stack while pushing(push if val <= mini.top()) and popping (pop from mini if val == mini.top() )\n\n```\nclass MinStack {\npublic:\n    stack<int> s;\n    stack<int> mini;\n    \n    void push(int val) {\n        if (mini.empty() || val <= mini.top())\n            mini.push(val);\n        s.push(val);    \n    }\n    \n    void pop() {\n        if (s.top() == mini.top())\n            mini.pop();\n        s.pop();\n    }\n    \n    int top() { return s.top(); }\n    int getMin() { return mini.top(); }\n};\n```\n#Approach 3: OPTIMAL: TIME O(1) SPACE O(1) //no extra space except the stack itself\n\n```\nclass MinStack {\npublic:\n    stack<int> s;\n    int mini = INT_MAX;\n    \n    void push(int val) {\n        if (val <= mini) //we\'ll push previous min value into the stack before pushing new min val, coz when we\'ll pop eg. min element then we need to update mini with prev min value   \n        {\n            s.push(mini); //we\'ll use it to update mini when popping min element!\n            mini = val; //update mini with min val\n        }\n        s.push(val);\n    }\n    \n    void pop() {\n        if (s.top() == mini) //this means mini got updated here, and we know that we have stored previous min value in stack before pushing new minimum!\n        {\n            s.pop(); //popping curr min value \n            mini = s.top(); //this is our previous min value, we\'ll update mini, and now we\'ll pop it as well!\n        }\n        s.pop();\n    }\n    \n    int top() {return s.top(); } \n    int getMin() { return mini; }\n};\n```
['Stack', 'C']