Python3 solution with O(1) time as expected
The insight is to keep track of the minimum value so far and push it, along with the number we are pushing, onto the stack.\n\nSo, in this implementation, we pu
The insight is to keep track of the minimum value so far and push it, along with the number we are pushing, onto the stack.\n\nSo, in this implementation, we push a tuple, with the first number being the number we are pushing, and the second being the minimum value so far. That way, retrieving the minimum value is also an O(1) operation.\n\n```\nclass MinStack:\n\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        self.__a = []\n\n    def push(self, x: int) -> None:\n        m = x\n        if self.__a:\n            m = self.__a[-1][1]\n            if m > x:\n                m = x\n        self.__a.append((x, m))\n\n    def pop(self) -> None:\n        self.__a.pop()\n        \n    def top(self) -> int:\n        return self.__a[-1][0]\n\n    def getMin(self) -> int:\n        return self.__a[-1][1]\n```
[]