C++ Simple code with one stack
I came up with this simple solution using just a single stack.\nHere I am using Stack of Pair of Int. The first value of the pair would store the element of the
I came up with this simple solution using just a single stack.\nHere I am using **Stack of Pair of Int**. The first value of the pair would store the element of the normal stack and the second value would store the minimum up to that point in the stack. \nSo even if the minimum element of the stack is removed from the top, we still have a backup of the next minimum element in the pair. So for every element pushed in the stack, it stores its corresponding minimum value.\n\nFor example, let\'s do a **Dry Run** of an example.\n```\n["MinStack","push","push","push","push","push","getMin","pop","pop","top","push","getMin"]\n[[],[5],[-2],[3],[-10],[20],[],[],[],[],[30],[]]\n```\n1. We push 5,-2,3,-10,20 in the stack.\n2. If the stack is empty we push {val,val} in the stack\n   else we push {val,min(s.top().second,val)} which is basically minimum upto that point.\n3. Hence {5,5},{-2,-2},{3,-2},{-10,-10},{20,-10} are pushed in the stack.\n4. To pop simply do stack.pop()\n5. To get the top return stack.top().first;\n6. Now we pop 20 and -10 from the stack\n    The elements in the stack would be {5,5},{-2,-2},{3,-2}\n7. On pushing 30 to the stack\n   The elements in the stack would be {5,5},{-2,-2},{3,-2},{30,-2}.\n\nThe **Output** of the code would be:\n```\n[null,null,null,null,null,null,-10,null,null,3,null,-2]\n```\n\nAll the operations are one liners expect the Push operation which is a 2 liner.\n```\nclass MinStack {\npublic:\n    vector< pair<int,int> > s;\n\t\n    MinStack() { }\n    \n    void push(int val) {\n        if(s.empty())\n            s.push_back({val,val});\n        else\n            s.push_back({val,min(s.back().second,val)});    \n    }\n    \n    void pop() { s.pop_back(); }\n    \n    int top() { return s.back().first; }\n    \n    int getMin() { return s.back().second; }\n};\n```\n```\nThe Time complexity of each operation is O(1)\nThe Space complexity is O(N)\n```\n\nGuys, please give an **upvote** to acknowledge the efforts of the writer.\nDo clarify your doubts in the comments section. Thank-you.
['Stack', 'C', 'C++']