【Video】dual data storage in stack
\n# Solution Video\n\nhttps://youtu.be/nejYpN3T8hw\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n\u25A0 
\n# Solution Video\n\nhttps://youtu.be/nejYpN3T8hw\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 10,623\nThank you for your support!\n\n---\n\n# Approach\n\n```python []\nclass MinStack:\n\n    def __init__(self):\n        self.st = []\n\n    def push(self, val: int) -> None:\n        min_val = self.getMin()\n        if min_val == None or min_val > val:\n            min_val = val\n        \n        self.st.append([val, min_val])\n\n    def pop(self) -> None:\n        self.st.pop()\n\n    def top(self) -> int:\n        return self.st[-1][0] if self.st else None\n\n    def getMin(self) -> int:\n        return self.st[-1][1] if self.st else None\n```\n```javascript []\nvar MinStack = function() {\n    this.st = [];\n};\n\n/** \n * @param {number} val\n * @return {void}\n */\nMinStack.prototype.push = function(val) {\n    let min_val = this.getMin();\n    if (min_val === null || min_val > val) {\n      min_val = val;\n    }\n    this.st.push([val, min_val]);\n};\n\n/**\n * @return {void}\n */\nMinStack.prototype.pop = function() {\n    this.st.pop();\n};\n\n/**\n * @return {number}\n */\nMinStack.prototype.top = function() {\n    return this.st.length ? this.st[this.st.length - 1][0] : null;\n};\n\n/**\n * @return {number}\n */\nMinStack.prototype.getMin = function() {\n    return this.st.length ? this.st[this.st.length - 1][1] : null;\n};\n```\n```java []\nclass MinStack {\n    private List<int[]> st;\n\n    public MinStack() {\n        st = new ArrayList<>();\n    }\n    \n    public void push(int val) {\n        int[] top = st.isEmpty() ? new int[]{val, val} : st.get(st.size() - 1);\n        int min_val = top[1];\n        if (min_val > val) {\n            min_val = val;\n        }\n        st.add(new int[]{val, min_val});        \n    }\n    \n    public void pop() {\n        st.remove(st.size() - 1);\n    }\n    \n    public int top() {\n        return st.isEmpty() ? -1 : st.get(st.size() - 1)[0];\n    }\n    \n    public int getMin() {\n        return st.isEmpty() ? -1 : st.get(st.size() - 1)[1];\n    }\n}\n```\n```C++ []\nclass MinStack {\nprivate:\n    vector<vector<int>> st;\n\npublic:\n    MinStack() {\n        \n    }\n    \n    void push(int val) {\n        int min_val = getMin();\n        if (st.empty() || min_val > val) {\n            min_val = val;\n        }\n        st.push_back({val, min_val});        \n    }\n    \n    void pop() {\n        st.pop_back();\n    }\n    \n    int top() {\n        return st.empty() ? -1 : st.back()[0];\n    }\n    \n    int getMin() {\n        return st.empty() ? -1 : st.back()[1]; \n    }\n};\n```\n---\n\n## **Understanding the Min Stack Design**\n\nWhen tackling the Min Stack problem, the challenge is to design a stack that supports standard operations like `push`, `pop`, and `top`, while also allowing retrieval of the minimum element in constant time. This requirement drives the design decisions in the solution, where simplicity and efficiency are key.\n\n### **Initialization: Keeping Track of the Stack State**\n\n```python\ndef __init__(self):\n    self.st = []\n```\n  - We start by initializing an empty list `self.st` to represent our stack. This stack will store both the value pushed and the minimum value at the time of pushing. By combining these two pieces of information in one stack, we avoid the need for a separate data structure to track the minimum values, leading to a more efficient and compact design.\n\n### **Push Operation: Managing Minimum Values**\n\n```python\ndef push(self, val: int) -> None:\n    min_val = self.getMin()\n    if min_val is None or min_val > val:\n        min_val = val\n        \n    self.st.append([val, min_val])\n```\n  - The `push` method needs to insert a new element into the stack while ensuring we can quickly access the minimum value.\n  - First, the current minimum value is retrieved using `self.getMin()`. If the stack is empty (i.e., `min_val` is `None`) or the new value is smaller than the current minimum, we update the minimum to be the new value.\n  - The stack then stores a pair `[val, min_val]`, where `val` is the actual value being pushed, and `min_val` is the minimum value up to that point in the stack. This dual storage allows the stack to maintain constant time complexity for retrieving the minimum value.\n\n### **Pop Operation: Simple Stack Behavior**\n\n```python\ndef pop(self) -> None:\n    self.st.pop()\n```\n  - The `pop` operation removes the most recent element from the stack, which includes both the value and the minimum value at that point. Since the stack inherently manages this pairing, no extra steps are needed to maintain the integrity of the minimum value tracking. This keeps the `pop` operation efficient and straightforward.\n\n### **Top Operation: Accessing the Latest Value**\n\n```python\ndef top(self) -> int:\n    return self.st[-1][0] if self.st else None\n```\n  - The `top` method returns the most recent value that was pushed onto the stack. Since each element in the stack is stored as a pair `[val, min_val]`, we access the actual value using `self.st[-1][0]`. If the stack is empty, it returns `None`, reflecting the absence of any elements.\n\n### **GetMin Operation: Constant-Time Minimum Retrieval**\n\n```python\ndef getMin(self) -> int:\n    return self.st[-1][1] if self.st else None\n```\n  - The primary challenge of the Min Stack is retrieving the minimum value in constant time. Thanks to the design choice of storing the minimum value alongside each element in the stack, the `getMin` method simply returns the second item in the most recent pair `[val, min_val]`. This ensures that no matter how many elements are in the stack, the minimum can always be accessed in O(1) time.\n\n### **Conclusion: Efficient Stack Management**\n\nThe Min Stack implementation cleverly combines the actual value and the current minimum into a single stack structure, ensuring that all operations\u2014`push`, `pop`, `top`, and `getMin`\u2014can be performed efficiently. This design decision not only simplifies the implementation but also guarantees that the stack meets the problem\'s requirements for constant-time minimum retrieval, making it an elegant and effective solution.\n\n---\n\nThank you for reading my post.\nPlease upvote it and don\'t forget to subscribe to my channel!\n\n# \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n# \u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n# \u2B50\uFE0F My previous post and video\n#48 - Rotate Image\n\nhttps://youtu.be/R1xO_Ear-ww\n
['C++', 'Java', 'Python3', 'JavaScript']