# Min [[stack|Stack]]
This is a seemingly easy problem, but it requires careful observation about properties of stack. Operations must be done in constant time, so we can rule out [[bst|BST]] and [[heap|min-heap]].
## Stack of Value/Minimum Pairs
Observe that an important **invariant** of stack is, given an element `v` on the stack, all elements below `v` will not change, as long as `v` remains on the stack.
Given this observation, we know that as long as `v` is at the top of stack, the minimum of stack is a fixed value. Therefore, to implement a min stack, instead of only storing the values, we store a pair of value and minimum.
```python
from dataclasses import dataclass
@dataclass(frozen=True)
class Pair:
v: int
m: int
class MinStack(list):
def push(self, v: int) -> None:
self.append(Pair(val, min(v, self[-1].m) if self else v))
def top(self) -> int:
return self[-1].v
def pop(self) -> int:
return super().pop().v
def getMin(self) -> int:
return self[-1].m
```
## Two Stacks
The pairs approach can be simplified, since the minimums can be quite repetitive. For example, when pushing values greater than existing min, the min will always stay the same.
We can instead maintaining two stacks, one for values, one for min. When the pushed value is also a minimum when it's pushed, we push it onto the `mstack` as well.
```python
def __init__(self) -> None:
self.vstack = []
self.mstack = []
def push(self, v: int) -> None:
self.vstack.append(v)
if not self.mstack or v <= self.mstack[-1]:
self.mstack.append(v)
def pop(self) -> int:
v = self.vstack[-1]
if v == self.mstack[-1]:
self.mstack.pop()
return v
def top(self) -> int:
return self.vstack[-1]
def getMin(self) -> int:
return self.mstack[-1]
```
## Improved Two Stacks
The two stacks approach is indeed better than pairs. However, when we keep pushing the same values, all of them will be also pushed to `mstack`, repeatedly.
It's easy to address, instead of pushing the same element, we simply increase the count of that min value.
```python
from dataclasses import dataclass
@dataclass()
class Pair:
v: int # minimum val
c: int = 1 # counts
class MinStack:
def __init__(self):
self.vstack = []
self.mstack = []
def push(self, v: int) -> None:
self.vstack.append(v)
if not self.mstack or v < self.mstack[-1].v:
self.mstack.append(Pair(v))
elif v == self.mstack[-1].v:
self.mstack[-1].c += 1
def pop(self) -> int:
v = self.vstack.pop()
if v == self.mstack[-1].v:
self.mstack[-1].c -= 1
if not self.mstack[-1].c:
self.mstack.pop()
return v
def top(self) -> int:
return self.vstack[-1]
def getMin(self) -> int:
return self.mstack[-1].v
```