✅ 🔥 4 ms Runtime Beats 96.78% User🔥||  Code Idea ✅ ||  Algorithm & Solving Step  ✅ ||
\n\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### Problem Intuition :\nThe goal is to design a stack that supports the following
![Screenshot 2024-12-02 at 8.29.35\u202FAM.png](https://assets.leetcode.com/users/images/4ac185a5-31b4-42e4-bac2-b78d0139999c_1733108430.9000807.png)\n\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n### **Problem Intuition** :\nThe goal is to design a stack that supports the following operations in **constant time** O(1) :\n- **`push(val)`**: Pushes `val` onto the stack.\n- **`pop()`**: Removes the element on top of the stack.\n- **`top()`**: Retrieves the top element of the stack.\n- **`getMin()`**: Retrieves the minimum element in the stack.\n\n---\n\n### **Code Idea** :\nWe need to keep track of the minimum element in the stack at all times. A simple stack won\'t allow efficient retrieval of the minimum in constant time. Therefore, we will use:\n- **A main stack** to store all values.\n- **A secondary stack** to store the current minimum element at each push operation. This secondary stack helps us keep track of the minimum value in O(1) .\n\n---\n\n### **Algorithm** :\n1. **Initialization**: Create two stacks:\n   - `mainStack`: Stores all elements.\n   - `minStack`: Tracks the minimum element.\n2. **Push**: Push the element to `mainStack`.\n   - Push the element to `minStack` if it is smaller than or equal to the top of `minStack`. If `minStack` is empty, push it.\n3. **Pop**: Remove the top element from `mainStack`.\n   - If this element is the same as the top of `minStack`, pop it from `minStack` as well.\n4. **Top**: Return the top of `mainStack`.\n5. **GetMin**: Return the top of `minStack`.\n\n---\n\n### **Complexity** :\n- **Time Complexity**:  O(1)  for all operations (push, pop, top, getMin).\n- **Space Complexity**:  O(n) , where n  is the number of elements in the stack.\n\n---\n\n### **Code Implementations** :\n\n#### **C++ Implementation** :\n```cpp\n#include <stack>\nusing namespace std;\n\nclass MinStack {\nprivate:\n    stack<int> mainStack;\n    stack<int> minStack;\n\npublic:\n    MinStack() {}\n\n    void push(int val) {\n        mainStack.push(val);\n        if (minStack.empty() || val <= minStack.top()) {\n            minStack.push(val);\n        }\n    }\n\n    void pop() {\n        if (mainStack.top() == minStack.top()) {\n            minStack.pop();\n        }\n        mainStack.pop();\n    }\n\n    int top() {\n        return mainStack.top();\n    }\n\n    int getMin() {\n        return minStack.top();\n    }\n};\n```\n\n---\n\n#### **Java Implementation** :\n```java\nimport java.util.Stack;\n\nclass MinStack {\n    private Stack<Integer> mainStack;\n    private Stack<Integer> minStack;\n\n    public MinStack() {\n        mainStack = new Stack<>();\n        minStack = new Stack<>();\n    }\n\n    public void push(int val) {\n        mainStack.push(val);\n        if (minStack.isEmpty() || val <= minStack.peek()) {\n            minStack.push(val);\n        }\n    }\n\n    public void pop() {\n        if (mainStack.peek().equals(minStack.peek())) {\n            minStack.pop();\n        }\n        mainStack.pop();\n    }\n\n    public int top() {\n        return mainStack.peek();\n    }\n\n    public int getMin() {\n        return minStack.peek();\n    }\n}\n```\n\n---\n\n#### **Python 3 Implementation** :\n```python\nclass MinStack:\n    def __init__(self):\n        self.mainStack = []\n        self.minStack = []\n\n    def push(self, val: int) -> None:\n        self.mainStack.append(val)\n        if not self.minStack or val <= self.minStack[-1]:\n            self.minStack.append(val)\n\n    def pop(self) -> None:\n        if self.mainStack[-1] == self.minStack[-1]:\n            self.minStack.pop()\n        self.mainStack.pop()\n\n    def top(self) -> int:\n        return self.mainStack[-1]\n\n    def getMin(self) -> int:\n        return self.minStack[-1]\n```\n\n---\n \n### **Example Walkthrough** :\n\n#### Example 1:\n**Input**:  \n```\n["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]\n[[], [-2], [0], [-3], [], [], [], []]\n```\n\n**Operations**:\n1. **`MinStack()`** \u2192 Initialize `mainStack` and `minStack`.\n2. **`push(-2)`**:\n   - `mainStack = [-2]`\n   - `minStack = [-2]`\n3. **`push(0)`**:\n   - `mainStack = [-2, 0]`\n   - `minStack = [-2]`\n4. **`push(-3)`**:\n   - `mainStack = [-2, 0, -3]`\n   - `minStack = [-2, -3]`\n5. **`getMin()`**:\n   - Returns `-3` (top of `minStack`).\n6. **`pop()`**:\n   - `mainStack = [-2, 0]`\n   - `minStack = [-2]` (since `-3` is popped).\n7. **`top()`**:\n   - Returns `0` (top of `mainStack`).\n8. **`getMin()`**:\n   - Returns `-2`.\n\n---\n![image.png](https://assets.leetcode.com/users/images/319076bc-cfe2-42de-bf7b-366af83317d3_1733108562.3525186.png)\n
['Stack', 'Design', 'C++', 'Java', 'Python3']