3 approaches (Two stack,  Only One Stack and linked list)
1. Using two stack : Pushing min element in s2\n\nTime: O(1) space: O(2n)\n\nCons: Extra O(n) space\n\nCode: \n\nclass MinStack {\npublic:\n    /** initialize y
**1. Using two stack : Pushing min element in s2**\n\nTime: O(1) space: O(2n)\n\n**Cons**: Extra O(n) space\n\n**Code**: \n```\nclass MinStack {\npublic:\n    /** initialize your data structure here. */\n    stack<int>s1, s2;\n    \n    void push(int x) {\n        if(s1.empty()){\n            s2.push(x);\n        }\n        else if(x <= s2.top()){\n            s2.push(x);\n        }\n        s1.push(x);\n    }\n    \n    void pop() {\n        if(s1.empty())return;\n        if(s1.top() == s2.top()){\n            s2.pop();\n        }\n        s1.pop();\n    }\n    \n    int top() {\n        if(s1.empty())return -1;\n        return s1.top();\n    }\n    \n    int getMin() {\n        if(s1.empty())return -1;\n        return s2.top();\n    }\n};\n\n```\n**2. Using a variable min_element:** \n\nTime: O(1) space: O(n)\n\n**Cons**: Integer overflow\n\n\n**Intuition**: mn variable will always hold minimum value but if it doesn\'t, it means s.top contains flag, so before popping the stack top, update the min. \n\n**Algo**: \n\t\t While pushing \n\t\t\t\t ```\n\t\t\t\t if x < mn : push 2*x-mn and put the provided x in mn\n\t\t\t\t ```\n\t\t Similarly while popping \n\t\t\t\t ```if s.top() < mn(indicates the flag): Restore the mn before popping: mn = 2* mn -s.top()```\n\t\t\t\t \n**Code**: \n```\nclass MinStack {\npublic:\n    /** initialize your data structure here. */\n    stack<long> s;\n    long mn;\n    MinStack() {\n        \n    }\n    \n    void push(int x) {\n        if(s.empty()){\n            s.push(x);\n            mn = x;\n        }\n        else if(x <= mn){\n            // put 2*x - mn into stack\n            s.push(2ll*x - mn);\n            mn = x;\n        }\n        else{\n            s.push(x);\n        }\n    }\n    \n    void pop() {\n        if(s.empty()) return;\n        // stack top can never be smaller than mn, if it is then it indicates a flag which means before popping, you have to update mn\n        if(s.top() < mn){\n            // mn = 2*mn - s.top()\n            mn = 2ll*mn - s.top();\n        }\n        s.pop();\n    }\n    \n    // critical part\n    int top() {\n        if(s.empty()) return -1;\n        if(s.top() < mn){\n            return mn;\n        }\n        return s.top();\n    }\n    \n    int getMin() {\n        if(s.empty()) return -1;\n        return mn;\n    }\n};\n\n```\n\n\n\n**3. Using a linked list:** \n\nTime: O(1) space: O(2n)\n\n**Cons**: O(2n) space since each node has two integer variable and there will be n such nodes\n\n**Algo:**\n```\n\t\ta. Make every new element the new head with updated min. \n\t\tb. And put the previous element next to the new head.\n```\n\n**Code**: \n```\nclass MinStack {\npublic:\n    struct Node{\n        int val, mn;\n        Node* next;\n        Node(int _val, int _mn, Node*_next = NULL){\n            val = _val;\n            mn = _mn;\n            next = _next;\n        }\n    }*head;\n    void push(int val) {\n        if(!head){\n            head = new Node(val, val);\n        } \n        else{\n            head = new Node(val, min(val, head->mn), head);\n        }\n    }\n    \n    void pop() {\n        if(!head) return ;\n        Node* temp = head;\n        head = head->next;\n        delete(temp);\n    }\n    \n    int top() {\n        if(!head) return -1;\n        return head->val;\n    }\n    \n    int getMin() {\n        if(!head) return -1;\n        return head->mn;\n    }\n};\n\n```\n**Which is the best solution from interview point of view?** \n\nFeel free to correct me!\nEdit: Space complexity added from valuable comments. \n
['Linked List', 'Stack', 'C', 'C++']