Simple and very short solution, O(1) time for all operations.
Very short solution and simple idea. Instead of keeping integer in the underlying stack, we also keep the min value for the moment item was pushed into the stac
Very short solution and simple idea. Instead of keeping integer in the underlying stack, we also keep the min value for the moment item was pushed into the stack. Think of it as a photography of the min value taken and stored with each value pushed into the stack at that moment.\n\nImplementation is trivial. The only line that needs explanation is below:\n\n```\nvoid push(int x) { s.push(Data(x, s.empty() ? x : min(x, s.top().min))); }\n```\n\nSo we take the minimum of last pushed item\'s min, or x itself, and x if the stack is yet empty.\n\nThis capturing technique is useful for a range of other problems as well. Hope it helps, and enjoy:\n\n```\nclass MinStack {\nprivate:\n    class Data {\n    public:\n        Data(int v, int m) : val(v), min(m) {}\n        int val;\n        int min;\n    };\n    stack<Data> s;\npublic:\n    void push(int x) { s.push(Data(x, s.empty() ? x : min(x, s.top().min))); }\n    void pop() { s.pop(); }\n    int top() { return s.top().val; }\n    int getMin() { return s.top().min; }\n};\n```
['C', 'C++']