[Python] O(1) time, stores only n+1 ints, Less space than 94%, One stack
Please feel free to ask questions or give suggestions. Upvote if you liked the solution.\n\nIdea: \n We keep track of the minimum element separately. \n For min
Please feel free to ask questions or give suggestions. **Upvote** if you liked the solution.\n\n**Idea**: \n* We keep track of the minimum element separately. \n* For minimums so far, instead of storing the value directly, we store a value less than minimum from which we can compute the minimum after this value has been removed. \n* Eg. say stack had minimum 3, and we wanted to push 1, we\'d push 2\\*val-min=-1 instead and save minimum as 1. Then, when we see the top of the stack is less than our minimum i.e. we\'re popping this element next, we can compute the minimum in stack after this has been popped as 2\\*min-stored_val=2\\*1-(-1)=3.\n* How this works: \n\t* Since val<min, 2\\*val<2*min=>2\\*val-min<min, everything greater than min is stored directly. \n\t* All values greater than min get stored directly. So, while popping, if we encounter a value smaller than min, it must be the value where min was in the stack and we stored 2\\*val-previous_min in stack.\n\t* When popping this value, 2\\*min-stored _val=2\\*min-(2\\*this_val-previous_min), but we stored this_val in min \n\t* So, 2\\*min-stored _val = previous_min.\n```\nclass MinStack:\n\n    def __init__(self):\n        # Note: Does not hold actual values for minimums encountered\n        self._stack = []\n        # Current minimum\n        self._min = None\n\n    def push(self, val: int) -> None:\n        # Note: Append here is amortised O(1), could use a different stack implementation for every call O(1). Logic remains same.\n        # Empty stack\n        if not self._stack:\n            self._stack.append(val)\n            self._min = val\n        # Normal add\n        elif val>=self._min:\n            self._stack.append(val)\n        # Val is min, add computed value that tells us the min when this is removed\n        else:\n            self._stack.append(2*val-self._min)\n            self._min = val     \n\n    def pop(self) -> None:\n        el = self._stack.pop()\n        # This was the minimum, extract the next minimum from value stored in stack\n        if el<self._min:\n            el, self._min = self._min, 2*self._min-el\n        return el\n\n    def top(self) -> int:\n        # stack[-1]>=min => stack[-1] is unmodified last pushed element, \n        # min>stack[-1] implies top is min and stack[-1] has computed value instead\n        return max(self._stack[-1], self._min)\n\n    def getMin(self) -> int:\n        return self._min\n```
[]