# LeetCode 895: Maximum Frequency Stack

## Problem Restatement

Design a data structure called `FreqStack`.

It must support two operations:

| Operation | Meaning |
|---|---|
| `push(val)` | Push integer `val` onto the stack |
| `pop()` | Remove and return the value with highest frequency |

If multiple values have the same highest frequency, `pop()` must remove and return the one that was pushed most recently.

So this is like a stack, but priority is based on:

1. Higher frequency first.
2. More recent push first when frequencies tie.

LeetCode guarantees that `pop()` is only called when the stack has at least one element. The constraints allow at most `2 * 10^4` calls to `push` and `pop`.

## Input and Output

| Item | Meaning |
|---|---|
| Constructor | `FreqStack()` creates an empty data structure |
| Input to `push` | Integer `val` |
| Output of `pop` | Integer removed from the stack |
| Main rule | Pop the most frequent value |
| Tie rule | If tied, pop the most recently pushed value |

Class shape:

```python
class FreqStack:

    def __init__(self):
        ...

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

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

## Examples

Example:

```text
Input:
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output:
[null, null, null, null, null, null, null, 5, 7, 5, 4]
```

Operations:

```python
freqStack = FreqStack()
freqStack.push(5)
freqStack.push(7)
freqStack.push(5)
freqStack.push(7)
freqStack.push(4)
freqStack.push(5)
```

Now the stack contains:

```text
[5, 7, 5, 7, 4, 5]
```

Frequencies:

| Value | Frequency |
|---|---:|
| `5` | 3 |
| `7` | 2 |
| `4` | 1 |

So the first `pop()` returns `5`.

After removing one `5`, frequencies become:

| Value | Frequency |
|---|---:|
| `5` | 2 |
| `7` | 2 |
| `4` | 1 |

Now `5` and `7` are tied, but `7` was pushed more recently than the remaining `5`, so the next `pop()` returns `7`.

The next pops return `5`, then `4`.

## First Thought: Scan the Whole Stack on Pop

A direct approach is to keep a normal stack list.

For `push`, append the value.

For `pop`, scan the entire stack to find:

1. The highest frequency.
2. Among values with that frequency, the most recent occurrence.

This works, but it makes `pop()` expensive.

If there are many operations, repeatedly scanning the whole stack can be too slow.

## Key Insight

Group values by their current frequency.

Maintain:

| Structure | Meaning |
|---|---|
| `freq[val]` | Current frequency of value `val` |
| `group[f]` | Stack of values that reached frequency `f` |
| `max_freq` | Current highest frequency in the data structure |

When we push a value:

1. Increase its frequency.
2. Push it into the stack for that new frequency.
3. Update `max_freq`.

When we pop:

1. Look at `group[max_freq]`.
2. Pop from that stack.
3. Decrease that value's frequency.
4. If `group[max_freq]` becomes empty, decrease `max_freq`.

This works because `group[f]` stores values in the order they reached frequency `f`. Therefore, the top of `group[max_freq]` is the most recently pushed value among all values with the highest frequency.

## Algorithm

Initialize:

```python
freq = {}
group = defaultdict(list)
max_freq = 0
```

For `push(val)`:

1. Increment `freq[val]`.
2. Let `f = freq[val]`.
3. Append `val` to `group[f]`.
4. Set `max_freq = max(max_freq, f)`.

For `pop()`:

1. Pop `val` from `group[max_freq]`.
2. Decrement `freq[val]`.
3. If `group[max_freq]` is empty, decrement `max_freq`.
4. Return `val`.

## Walkthrough

Push sequence:

```text
5, 7, 5, 7, 4, 5
```

After all pushes:

| Frequency | Stack |
|---|---|
| `1` | `[5, 7, 4]` |
| `2` | `[5, 7]` |
| `3` | `[5]` |

`max_freq = 3`.

First `pop()`:

```text
group[3].pop() -> 5
```

Now `group[3]` is empty, so `max_freq` becomes `2`.

Second `pop()`:

```text
group[2].pop() -> 7
```

This returns `7`, because among values with frequency `2`, `7` reached that frequency most recently.

Third `pop()`:

```text
group[2].pop() -> 5
```

Now `group[2]` is empty, so `max_freq` becomes `1`.

Fourth `pop()`:

```text
group[1].pop() -> 4
```

The return sequence is:

```text
5, 7, 5, 4
```

## Correctness

The dictionary `freq` always stores the current number of active occurrences for each value.

When `push(val)` is called, the value gains one occurrence, so increasing `freq[val]` is correct. If the new frequency is `f`, appending `val` to `group[f]` records that this push made `val` reach frequency `f`.

For any frequency `f`, `group[f]` is a stack ordered by the time values reached frequency `f`. Therefore, the last value in `group[f]` is the most recent value among all values that currently have reached that frequency and have not yet been removed from that frequency group.

`max_freq` stores the highest current frequency. Therefore, `group[max_freq]` contains the correct candidates for `pop()`.

When `pop()` removes the top value from `group[max_freq]`, it selects a value with highest frequency. Since it pops from a stack, it also selects the most recent value among ties.

After removal, that value's active frequency decreases by one. If no values remain in the old maximum frequency group, then the highest active frequency decreases by one.

Thus, each `pop()` returns exactly the value required by the problem.

## Complexity

| Operation | Time | Why |
|---|---:|---|
| Constructor | `O(1)` | Initializes maps and counter |
| `push` | `O(1)` | Hash map update and list append |
| `pop` | `O(1)` | List pop and hash map update |

Space complexity is `O(n)`, where `n` is the number of active pushed elements plus stored frequency-group entries.

## Implementation

```python
from collections import Counter, defaultdict

class FreqStack:

    def __init__(self):
        self.freq = Counter()
        self.group = defaultdict(list)
        self.max_freq = 0

    def push(self, val: int) -> None:
        self.freq[val] += 1
        f = self.freq[val]

        self.group[f].append(val)

        if f > self.max_freq:
            self.max_freq = f

    def pop(self) -> int:
        val = self.group[self.max_freq].pop()

        self.freq[val] -= 1

        if not self.group[self.max_freq]:
            self.max_freq -= 1

        return val
```

## Code Explanation

We use `freq` to count current frequencies:

```python
self.freq = Counter()
```

We use `group` to store one stack per frequency:

```python
self.group = defaultdict(list)
```

We track the current highest frequency:

```python
self.max_freq = 0
```

On push, we update the value's frequency:

```python
self.freq[val] += 1
f = self.freq[val]
```

Then we append the value to the stack for that frequency:

```python
self.group[f].append(val)
```

On pop, we remove the most recent value from the highest-frequency stack:

```python
val = self.group[self.max_freq].pop()
```

Then we decrease its active frequency:

```python
self.freq[val] -= 1
```

If the highest-frequency stack is empty, no value currently has that frequency anymore:

```python
if not self.group[self.max_freq]:
    self.max_freq -= 1
```

Finally, return the removed value.

## Testing

```python
def run_tests():
    fs = FreqStack()

    fs.push(5)
    fs.push(7)
    fs.push(5)
    fs.push(7)
    fs.push(4)
    fs.push(5)

    assert fs.pop() == 5
    assert fs.pop() == 7
    assert fs.pop() == 5
    assert fs.pop() == 4

    fs = FreqStack()
    fs.push(1)
    fs.push(2)
    fs.push(3)

    assert fs.pop() == 3
    assert fs.pop() == 2
    assert fs.pop() == 1

    fs = FreqStack()
    fs.push(1)
    fs.push(1)
    fs.push(2)
    fs.push(2)

    assert fs.pop() == 2
    assert fs.pop() == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official-style sequence | Checks frequency and recency tie-breaking |
| All frequencies equal | Behaves like normal stack |
| Equal high frequencies | Most recent among tied values is popped first |