# LeetCode: MinStack
Yet another solution to a very simple exercise.
# Problem
One of the exercises proposed in the third chapter of _The Algorithm Design Manual_[^skiena] is this one:
> **3-4.** Design a stack _S_ that supports _S.push(x)_, _S.pop()_, and _S.findmin()_, which returns the minimum element of _S_. All operations should run in constant time.
Right now it seems that the [website of the book](https://www.algorist.com/algowiki/index.php/Chapter_3) doesn't provide a solution (most likely because it is a pretty simple one).
Anyway, this exercise is also provided by [LeetCode](https://leetcode.com/problems/min-stack/).
## Some solutions
An obvious path to follow to solve this problem is to create a stack and to use an external variable to handle the _minimum value_, taking care to update it after every `push(x)` and most of all after every `pop(x)`. Yet, this leaves us with a new issue: if the `pop(x)` interests that _minimum value_, how do we track the _previous minimum value_, so that we can serve it when `getMin()` is called?
I realised most people do like this: they create a **second** stack; when pushing a new value they insert whatever is smallest between the one they are inserting and the last _minimum value_ recorded.
For instance this is the code that [this brilliant youtube channel](https://www.youtube.com/watch?v=qkLl7nAwDPo) proposes:
```python
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
val = min(val, self.minStack[-1] if self.minStack else val)
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
```
Oh yes, it works and it does so even in time complexity $\mathcal{O}(1)$, as requested in the assignment!
Other similar approaches exist in the _Discussion_ section of LeetCode[^leetcode].
### Issues with these approaches
The above method carries a burden: the size of the second stack grows linearly with the length of the main one, doubling the memory usage.
# Another way
We still create the two stacks.
At the start, both of them are empty: during the first `push(x)` we add the same value to both stacks.
During the following `push(x)` calls we will be more careful: we always add the value to `self.stack`, nonetheless in the stack tracking the minimum values (in my code that's `self.minS`) we save only the `val` if it is smaller or equal to the last element contained in `self.minS`.
When we `pop()`[^constraint] a value from the main stack (`self.stack`) we delete it from `self.minS` only if the `val` popped is the same as the last value saved in `self.minS`.
By operating in this way we are guaranteed that `self.minS` saves the minimum values in decrescent mode, being always certain to work in $\mathcal{O}(1)$ without duplicating (in the average case and when the stack grows) our memory footprint.
This is the naïve implementation:
```python
class MinStack:
def __init__(self):
self.stack = []
self.minS = []
def push(self, val: int) -> None:
# Initially both stacks are empty
if not self.stack:
self.stack.append(val)
self.minS.append(val)
else:
if val <= self.minS[-1]:
self.minS.append(val)
self.stack.append(val)
def pop(self) -> None:
popped = self.stack.pop()
# We delete the last only if it is
# equal to the minimum value
if popped == self.minS[-1]:
del self.minS[-1]
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minS[-1]
```
## Comparing the two approaches
In order to see how the different approaches behave with larger values of _n_, the following set of instructions have been fed through the `cProfile` python [module](https://docs.python.org/3/library/profile.html).
```python
def run():
obj = MinStack()
attempts = 1_000_000
min_len, stack_len = 0, 0
for i in range(attempts):
x = random.randint(-100, 100)
obj.push(x)
obj.top()
obj.getMin()
min_len += len(obj.minStack) # or obj.minS
stack_len += len(obj.stack)
# we want to pop less often, to highlight the
# differences (when push(x) and pop() aren't simmetrical)
if x % 2 == 0:
obj.pop()
print(f"Avg length of obj.minStack: {min_len/attempts}")
print(f"Avg length of obj.minS: {stack_len/attempts}")
```
To be noted that:
* as a random int is inserted during the loop, results will vary slightly;
* `min_len` and `stack_len` are incremented before `pop()` on purpose;
* we want the size of the stack to grow (`pop()` must happen less frequently than `push(x)`), otherwise it's granted that both stacks will always have the same length.
### Before
The first solution explored above generates the following result:
```sh
Avg length of obj.minStack: 249034.230154
Avg length of obj.minS: 249034.230154
17781331 function calls in 5.594 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1000000 0.661 0.000 1.045 0.000 005-a.py:10(push)
502392 0.224 0.000 0.309 0.000 005-a.py:15(pop)
1000000 0.122 0.000 0.122 0.000 005-a.py:19(top)
1000000 0.118 0.000 0.118 0.000 005-a.py:22(getMin)
1 1.595 1.595 5.587 5.587 005-a.py:25(run)
# Omitting irrelevant functions here
```
Of course with the first method the two stacks have always the same length. The whole function took **5.59 seconds**.
When submitted to LeetCode it returned:
### After
Let's do the same for our script and explore the size of the stacks as we did before:
```
Avg length of obj.minS: 2497.844128
Avg length of obj.minS: 249004.41381
15287241 function calls in 4.740 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1000000 0.363 0.000 0.454 0.000 005-b.py:10(push)
502262 0.174 0.000 0.218 0.000 005-b.py:21(pop)
1000000 0.118 0.000 0.118 0.000 005-b.py:29(top)
1000000 0.114 0.000 0.114 0.000 005-b.py:32(getMin)
```
I'm not that impressed by the improvement, albeit minor, in speed (a marginal **4.74 seconds**), but by the reduction (two orders of magnitude[^n]) in the average length of `self.minS`!
At submission, even LeetCode noticed the improvement[^now].
___
Last version: [8365627B0DCFEDF1B17B77EB4F33EB6C99ABB1BD26BF4FA7CDB57F9FAB1E6BA6](https://etherscan.io/tx/0xa96d36a94f0d33f346da1b3d924582ec848d7e92292dd63161239b08fed89a91#eventlog).
[^skiena]: See [_The Algorithm Design Manual_](https://link.springer.com/book/10.1007/978-3-030-54256-6?gclid=Cj0KCQiA-rj9BRCAARIsANB_4AB7klvO1OATIn19oOb6P4p9LMchYhs_1PrUIcrLdxlvgcc3Axu1McUaAng7EALw_wcB) by Steven Skiena (Springer, 2020).
[^leetcode]: Another example using _deque_ is [here](https://leetcode.com/problems/min-stack/discuss/2812426/Python-Solution-With-Explanation).
[^constraint]: To be noted: the interface of the `MinStack` class, as defined by LeetCode, doesn't require us to return the popped value.
[^now]: At the moment of writing of this post.
[^n]: For these values of _n_.