21.1 (Approach 1) | O(n)✅ | Python & C++(Step by step explanation)✅
Intuition\n Describe your first thoughts on how to solve this problem. \nThe idea is to maintain two stacks: one for the regular stack operations, and another t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe idea is to maintain two stacks: one for the regular stack operations, and another to keep track of the minimum element at each step.\n\n# Approach\n1. **Initialize two stacks: `stack` and `minStack`.**\n   - We use two separate stacks to maintain regular operations (`stack`) and to keep track of the minimum element (`minStack`).\n\n2. **When pushing a value:**\n   - Compare the current value with the current minimum in `minStack`.\n   - Push the minimum of the current value and the current minimum onto `minStack`.\n   - This ensures that `minStack` always reflects the minimum element at each step.\n\n3. **When popping:**\n   - Perform the pop operation on both `stack` and `minStack`.\n   - This ensures that the stacks stay synchronized, and the minimum element is correctly updated.\n\n4. **For retrieving the top element:**\n   - Use the top operation on `stack` to get the element at the top of the regular stack.\n\n5. **For retrieving the minimum element:**\n   - Use the top operation on `minStack` to get the minimum element at the current step.\n\nThis approach ensures that, at any point in time, the `minStack` maintains the minimum element corresponding to the current state of the regular `stack`. The synchronization between the two stacks allows for constant time complexity in retrieving the minimum element along with other standard stack operations.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(1)$$ for each operation. -->\n   - Push, pop, top, and getMin operations all have constant time complexity.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ due to the two stacks. -->\n   - The space complexity is proportional to the number of elements in the stack, so it is $$O(n)$$.\n\n\n# Code(Python)\n```python\n# Python Implementation\nclass MinStack:\n    def __init__(self):\n        # Initialize two stacks: one for regular elements and one for maintaining the minimum at each step.\n        self.stack = []\n        self.minStack = []\n\n    def push(self, val: int) -> None:\n        # Push the value onto the regular stack.\n        self.stack.append(val)\n        # Update the value to be pushed onto the minimum stack, considering the current minimum.\n        val = min(val, self.minStack[-1] if self.minStack else val)\n        # Push the updated value onto the minimum stack.\n        self.minStack.append(val)\n\n    def pop(self) -> None:\n        # Pop elements from both stacks to maintain synchronization.\n        self.stack.pop()\n        self.minStack.pop()\n\n    def top(self) -> int:\n        # Retrieve the top element from the regular stack.\n        return self.stack[-1]\n\n    def getMin(self) -> int:\n        # Retrieve the top element from the minimum stack, representing the current minimum.\n        return self.minStack[-1]\n\n```\n\n# Code(C++)\n```c++\n\n\n# C++ Implementation\nclass MinStack {\npublic:\n    stack<int> arr;       // Regular stack for elements.\n    stack<int> min_arr;   // Stack for maintaining the minimum at each step.\n\n    MinStack() {\n        // Constructor.\n    }\n    \n    void push(int val) {\n        // Push the value onto the regular stack.\n        arr.push(val);\n        // Update the value to be pushed onto the minimum stack, considering the current minimum.\n        if (!min_arr.empty()) {\n            val = min(val, min_arr.top());\n        }\n        // Push the updated value onto the minimum stack.\n        min_arr.push(val);\n    }\n    \n    void pop() {\n        // Pop elements from both stacks to maintain synchronization.\n        arr.pop();\n        min_arr.pop();\n    }\n    \n    int top() {\n        // Retrieve the top element from the regular stack.\n        return arr.top();\n    }\n    \n    int getMin() {\n        // Retrieve the top element from the minimum stack, representing the current minimum.\n        return min_arr.top();\n    }\n};\n\n```\n\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)
['Stack', 'C++', 'Python3']