> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Maximum Frequency Stack Python Solution

> Tested Python solution for LeetCode 895 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 895, Hard. Topics: Hash Table, Stack, Design, Ordered Set. [View on LeetCode](https://leetcode.com/problems/maximum-frequency-stack/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 895   # by problem number
lcpy gen -s maximum_frequency_stack   # by problem name
```

## Problem

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the `FreqStack` class:

* `FreqStack()` constructs the empty frequency stack.
* `void push(int val)` pushes an integer `val` onto the top of the stack.
* `int pop()` removes and returns the most frequent element in the stack.
  * If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

### Examples

```
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]
```

**Explanation:**

```
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
```

### Constraints

* `0 <= val <= 10^9`
* At most `2 * 10^4` calls will be made to `push` and `pop`.
* It is guaranteed that there will be at least one element in the stack before calling `pop`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_frequency_stack/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_frequency_stack/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class FreqStack:
    def __init__(self) -> None:
        self.freq: dict[int, int] = {}
        self.group: dict[int, list[int]] = {}
        self.max_freq = 0

    # Time: O(1)
    # Space: O(n)
    def push(self, val: int) -> None:
        count = self.freq.get(val, 0) + 1
        self.freq[val] = count
        if count > self.max_freq:
            self.max_freq = count
        self.group.setdefault(count, []).append(val)

    # Time: O(1)
    # Space: O(n)
    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
```

## Complexity

| Time | Space |
| ---- | ----- |
| O(1) | O(n)  |

## Tags

[Grind](/catalog/grind), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).