Intuition
The main difficulty in reaching time complexity is in tracking the minimum. To achieve this, notice that you can simply save the minimum in any point in time. For example, if we push [3, 1, 2], then the minimum stack will be [3, 1, 1]. Then, when you pop 2, you pop off 1, and 1 is still the minimum. This maintains order.
Complexity
Runtime
Space
Code
class MinStack:
def __init__(self):
self.min_tracker = []
self.stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if len(self.min_tracker) == 0:
self.min_tracker.append(val)
elif self.min_tracker[-1] >= val:
self.min_tracker.append(val)
def pop(self) -> None:
tmp = self.stack.pop()
if len(self.min_tracker) > 0 and self.min_tracker[-1] == tmp:
self.min_tracker.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_tracker[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()Cards
START Basic Front: Min Stack Back: if we push [3, 1, 2], then the minimum stack will be [3, 1, 1] END