> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/maximum-frequency-stack.md).

# Maximum Frequency Stack

Implement `FreqStack`, a class which simulates the operation of a stack-like data structure.

`FreqStack` has two functions:

* `push(int x)`, which pushes an integer `x` onto the stack.
* `pop()`, which **removes** and returns the most frequent element in the stack.
  * If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

**Example 1:**

```
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:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].
```

**Note:**

* Calls to `FreqStack.push(int x)` will be such that `0 <= x <= 10^9`.
* It is guaranteed that `FreqStack.pop()` won't be called if the stack has zero elements.
* The total number of `FreqStack.push` calls will not exceed `10000` in a single test case.
* The total number of `FreqStack.pop` calls will not exceed `10000` in a single test case.
* The total number of `FreqStack.push` and `FreqStack.pop` calls will not exceed `150000` across all test cases.

```java
class FreqStack {
    // Map of element -> frequency
    HashMap<Integer, Integer> freq;
    // Map of frequency -> stack of elements with this frequency
    HashMap<Integer, Stack<Integer>> m;
    int maxFreq;

    public FreqStack() {
        freq = new HashMap<>();
        m = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        maxFreq = Math.max(maxFreq, f);
        if (!m.containsKey(f))
            m.put(f, new Stack<Integer>());
        m.get(f).add(x);
    }

    // Remember that map of all the frequencies upto the maxFreq exists
    // Because when we promote an element from freq to freq+1
    // then we are not actually removing that element from that stack
    public int pop() {
        int x = m.get(maxFreq).pop();
        freq.put(x, maxFreq - 1);
        if (m.get(maxFreq).size() == 0)
            maxFreq--;
        return x;
    }
}
```