[Python] ✅ || Easy Mind Map Diagram || Beginner-Friendly Design || All Operations - [Time O(1)]
\n# Intuition\n\nWhen faced with the problem of designing a stack that can return its minimum element in constant time, I thought of maintaining a secondary str
\n# Intuition\n\nWhen faced with the problem of designing a stack that can return its minimum element in constant time, I thought of maintaining a secondary structure to keep track of the minimum elements. This structure should update in tandem with the main stack and allow retrieval of the current minimum without needing to scan through the entire stack.\n\n![Screenshot 2024-01-09 at 6.13.38\u202FPM.png](https://assets.leetcode.com/users/images/5e133db4-5bf7-4c74-9c33-f93e16545920_1704842593.2901525.png)\n\n\n# Approach\n\nThe solution employs two stacks: `self.stack` for regular stack operations and `self.stack_desc` for tracking the minimum element. When a new element is pushed:\n- It is always added to `self.stack`.\n- It is added to `self.stack_desc` only if it is less than or equal to the current minimum (top of `self.stack_desc`).\n\nWhen an element is popped:\n- It is removed from `self.stack`.\n- If the popped element is the current minimum (top of `self.stack_desc`), it is also removed from `self.stack_desc`.\n\nThis ensures that `self.stack_desc` always contains the current minimum at its top, allowing the `getMin` function to return the minimum in O(1) time.\n\n# Complexity\n\n- **Time complexity**: $$O(1)$$\n  - All operations (`push`, `pop`, `top`, `getMin`) are performed in constant time.\n- **Space complexity**: $$O(n)$$\n  - In the worst case (when all elements are pushed in decreasing order), `self.stack_desc` will have as many elements as `self.stack`, leading to a space complexity of $$O(n)$$.\n  - In contrast, if the elements are pushed in increasing order, it represents a best-case scenario for `self.stack_desc`, as only the first element (the smallest one) will be in `self.stack_desc` and the rest will not meet the condition to be pushed onto it.\n\n# Code\n\n```python\nclass MinStack:\n\n    def __init__(self):\n        self.stack = []\n        self.stack_desc = []\n        \n    def push(self, val: int) -> None:\n        self.stack.append(val)\n        if not self.stack_desc or val <= self.stack_desc[-1]:\n            self.stack_desc.append(val)\n        \n    def pop(self) -> None:\n        if self.stack.pop() == self.stack_desc[-1]:\n            self.stack_desc.pop()\n        \n    def top(self) -> int:\n        return self.stack[-1]\n        \n    def getMin(self) -> int:\n        return self.stack_desc[-1]\n\n# Your MinStack object will be instantiated and called as such:\n# obj = MinStack()\n# obj.push(val)\n# obj.pop()\n# param_3 = obj.top()\n# param_4 = obj.getMin()\n```
['Stack', 'Design', 'Python3']