# LeetCode 155: Min Stack

## Problem Restatement

We need to design a stack that supports normal stack operations and also returns the minimum element currently inside the stack.

The class must support these methods:

| Method | Meaning |
|---|---|
| `MinStack()` | Initialize the stack |
| `push(val)` | Push `val` onto the stack |
| `pop()` | Remove the top element |
| `top()` | Return the top element |
| `getMin()` | Return the minimum element in the stack |

Each operation must run in `O(1)` time. LeetCode states that `pop`, `top`, and `getMin` will only be called on non-empty stacks, and at most `3 * 10^4` calls will be made.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sequence of stack operations |
| Output | Return values from `top()` and `getMin()` |
| Main requirement | Every operation must be `O(1)` |
| Value range | `-2^31 <= val <= 2^31 - 1` |

Example class shape:

```python
class MinStack:

    def __init__(self):
        ...

    def push(self, val: int) -> None:
        ...

    def pop(self) -> None:
        ...

    def top(self) -> int:
        ...

    def getMin(self) -> int:
        ...
```

## Examples

Use this operation sequence:

```python
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
minStack.getMin()
minStack.pop()
minStack.top()
minStack.getMin()
```

After pushing `-2`, `0`, and `-3`, the stack is:

```python
[-2, 0, -3]
```

The minimum is:

```python
-3
```

After `pop()`, the stack becomes:

```python
[-2, 0]
```

The top is:

```python
0
```

The minimum is now:

```python
-2
```

## First Thought: Normal Stack Plus Scan

A normal stack can support `push`, `pop`, and `top` in `O(1)` time.

For `getMin()`, the simplest idea is to scan the whole stack.

```python
class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return min(self.stack)
```

This is correct, but `getMin()` takes `O(n)` time.

The problem requires constant time for every operation, so scanning is too slow.

## Key Insight

When we push a value, we can also remember the minimum value at that exact stack depth.

For example, after these pushes:

```python
push(-2)
push(0)
push(-3)
```

The normal stack is:

```python
[-2, 0, -3]
```

The current minimum after each push is:

```python
[-2, -2, -3]
```

So we maintain two stacks:

| Stack | Meaning |
|---|---|
| `stack` | Stores the actual values |
| `min_stack` | Stores the minimum value at each depth |

The top of `min_stack` always gives the current minimum.

That makes `getMin()` an `O(1)` operation.

## Algorithm

Initialize two empty lists:

```python
self.stack = []
self.min_stack = []
```

For `push(val)`:

1. Push `val` onto `stack`.
2. Compute the new minimum.
3. Push that minimum onto `min_stack`.

If `min_stack` is empty, the new minimum is `val`.

Otherwise, the new minimum is:

```python
min(val, self.min_stack[-1])
```

For `pop()`:

1. Pop from `stack`.
2. Pop from `min_stack`.

The two stacks must stay the same length.

For `top()`:

```python
return self.stack[-1]
```

For `getMin()`:

```python
return self.min_stack[-1]
```

## Walkthrough

Start with empty stacks:

| Operation | `stack` | `min_stack` | Return |
|---|---|---|---|
| `push(-2)` | `[-2]` | `[-2]` | |
| `push(0)` | `[-2, 0]` | `[-2, -2]` | |
| `push(-3)` | `[-2, 0, -3]` | `[-2, -2, -3]` | |
| `getMin()` | `[-2, 0, -3]` | `[-2, -2, -3]` | `-3` |
| `pop()` | `[-2, 0]` | `[-2, -2]` | |
| `top()` | `[-2, 0]` | `[-2, -2]` | `0` |
| `getMin()` | `[-2, 0]` | `[-2, -2]` | `-2` |

Notice that `min_stack` changes in sync with `stack`.

When the top value is removed, the saved minimum for that old stack depth is also removed.

## Correctness

The invariant is:

After every operation, `min_stack[i]` stores the minimum value among `stack[0]` through `stack[i]`.

When we push a new value `val`, the minimum at the new top can only be either:

1. The new value `val`
2. The previous minimum, stored at `min_stack[-1]`

So pushing `min(val, self.min_stack[-1])` preserves the invariant.

When we pop, both stacks remove their top values. The stack returns to the previous depth, and `min_stack[-1]` again stores the minimum for that previous depth.

Because the invariant is always true, `getMin()` can return `min_stack[-1]`, which is exactly the minimum value in the current stack.

`top()` returns `stack[-1]`, which is the most recently pushed value that has not been popped.

Therefore, every method returns the correct result.

## Complexity

Let `n` be the number of elements currently in the stack.

| Operation | Time | Why |
|---|---|---|
| `push` | `O(1)` | Appends to two lists |
| `pop` | `O(1)` | Pops from two lists |
| `top` | `O(1)` | Reads the last element |
| `getMin` | `O(1)` | Reads the last saved minimum |

| Metric | Value | Why |
|---|---|---|
| Space | `O(n)` | We store the values and one saved minimum per value |

## Implementation

```python
class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

        if self.min_stack:
            current_min = min(val, self.min_stack[-1])
        else:
            current_min = val

        self.min_stack.append(current_min)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]
```

## Code Explanation

The constructor creates two stacks:

```python
self.stack = []
self.min_stack = []
```

The main stack stores real values.

The second stack stores the running minimum at every depth.

When pushing a value:

```python
self.stack.append(val)
```

we first add it to the normal stack.

Then we compute the minimum after this push:

```python
if self.min_stack:
    current_min = min(val, self.min_stack[-1])
else:
    current_min = val
```

If there was already a minimum, compare it with the new value.

If the stack was empty, the new value itself is the minimum.

Then store that minimum:

```python
self.min_stack.append(current_min)
```

When popping:

```python
self.stack.pop()
self.min_stack.pop()
```

we remove from both stacks so their depths remain aligned.

The top value is:

```python
return self.stack[-1]
```

The current minimum is:

```python
return self.min_stack[-1]
```

## Testing

```python
def run_tests():
    s = MinStack()

    s.push(-2)
    s.push(0)
    s.push(-3)
    assert s.getMin() == -3

    s.pop()
    assert s.top() == 0
    assert s.getMin() == -2

    s.push(-5)
    assert s.getMin() == -5

    s.pop()
    assert s.getMin() == -2

    s.pop()
    assert s.top() == -2
    assert s.getMin() == -2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Push `-2`, `0`, `-3` | Checks decreasing minimum |
| Pop after minimum | Checks minimum restoration |
| Push `-5` | Checks new smaller value |
| Pop `-5` | Checks previous minimum returns |
| Final top and min | Checks stack alignment |