Min Stack - Solution
Solutions and explanations
class MinStack:
def __init__(self):
self.stack = [] # Stack of Tuples (value, minimum)
def push(self, val: int) -> None:
cur_min = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, cur_min))
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][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()
Complexity Analysis
Here, n is the elements pushed on the stack.
- Time Complexity:
O(1)per operation invocation- Each operation (push, pop, top, getMin) takes constant time because the minimum is stored with each element.
- Space Complexity:
O(n)- In the worst case, the stack may store up to
nelements, where each element stores both its value and the current minimum.
- In the worst case, the stack may store up to