Min Stack
- 1 min read
- Stacks
- LC-Medium
3 years ago
Solution
-
YOU DON'T NEED TO MAINTAIN A CURRENT MIN IN THE CLASS VARIABLE!! USE THE SECOND ELEMENT OF THE STACK TOP!!!
-
Maintain a stack with two elements, the first one the actual value and the second value is the minimum value in the stack at that point in time.
-
You can also use two stacks but this solution is a bit more neater.
-
To visualize:
-
For the first element, (15, 2): From the right (i.e. stack top), it just means that for all elements below 15, up until 2, the minimum is 2.
| Time | Space | Explanation |
|---|---|---|
O(1) | O(n) | TC is O(1) for all operations, space is not extra, it's just for the items stored |
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
min = val
if self.stack != [] and self.stack[-1][1] < min:
min = self.stack[-1][1]
self.stack.append((val, min))
def pop(self) -> None:
return self.stack.pop()[0]
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]