155: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nTo implement the MinStack, we can use two stacks. One stack will store th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTo implement the MinStack, we can use two stacks. One stack will store the actual elements, and the other stack will store the minimum values seen so far. When we push a new element onto the stack, we check if it\'s smaller than the current minimum value, and if so, we push it onto the minimum stack. When we pop an element from the stack, we also pop the corresponding element from the minimum stack if it\'s the current minimum value.\n\nLet\'s go through the time and space complexity analysis for each function:\n\n- push: O(1) time complexity for pushing an element onto the main stack and the minimum stack, and O(1) space complexity for storing the two stacks.\n- pop: O(1) time complexity for popping an element from the main stack and the minimum stack, and O(1) space complexity for the two stacks.\n- top: O(1) time complexity for returning the top element of the main stack, and O(1) space complexity for the two stacks.\n- getMin: O(1) time complexity for returning the minimum value from the minimum stack, and O(1) space complexity for the two stacks.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass MinStack:\n    def __init__(self):\n        self.stack = []  # initialize main stack\n        self.min_stack = []  # initialize minimum value stack\n\n    def push(self, val: int) -> None:\n        self.stack.append(val)  # push value onto main stack\n        if not self.min_stack or val <= self.min_stack[-1]:  # if minimum stack is empty or the value is smaller or equal to current minimum\n            self.min_stack.append(val)  # push value onto minimum stack\n\n    def pop(self) -> None:\n        if self.stack:  # check if main stack is not empty\n            if self.stack[-1] == self.min_stack[-1]:  # if the element to pop is the current minimum\n                self.min_stack.pop()  # pop from minimum stack\n            self.stack.pop()  # always pop from main stack\n\n    def top(self) -> int:\n        if self.stack:  # check if main stack is not empty\n            return self.stack[-1]  # return the top element\n\n    def getMin(self) -> int:\n        if self.min_stack:  # check if minimum stack is not empty\n            return self.min_stack[-1]  # return the current minimum value\n\n```
['Stack', 'Design', 'Python', 'Python3']