# Maximum Frequency Stack
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-frequency-stack)
Canonical: https://scaleengineer.com/dsa/problems/maximum-frequency-stack
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, Stack, Ordered Set
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix), [PayPal](https://scaleengineer.com/companies/paypal), [Salesforce](https://scaleengineer.com/companies/salesforce), [Snap](https://scaleengineer.com/companies/snap)
---
## 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 an 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.

**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**
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 <= 109`
* At most `2 * 104` 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`.

# Approaches
## Brute Force with Linear Scan
This is a straightforward, brute-force approach that directly simulates the requirements using basic data structures. We use a list to act as our stack. The `push` operation is simple, just adding an element to the list. The main work is done in the `pop` operation, which requires recalculating all element frequencies from scratch, finding the maximum frequency, and then scanning the list again to find the correct element to remove. This leads to a linear time complexity for `pop`.
**Time:** - `push(val)`: O(1) amortized time.
- `pop()`: O(N) time, where N is the number of elements in the stack. This is because we perform two passes over the stack in the worst case. · **Space:** O(N), where N is the number of elements in the stack. This space is used to store the elements themselves. The `pop` operation requires additional O(U) space for the frequency map, where U is the number of unique elements (U <= N).
**Pros:** Simple to understand and implement.; Uses only basic and common data structures.
**Cons:** The `pop` operation is very inefficient with a time complexity of `O(N)`, where `N` is the number of elements in the stack.; Removing an element from the middle of an `ArrayList` is also an `O(N)` operation, further contributing to the poor performance.; It is not suitable for scenarios with a large number of elements or frequent `pop` calls.
### Explanation
In this approach, we maintain the stack's elements in an `ArrayList`. When `push(val)` is called, we add `val` to the end of this list, which is an `O(1)` operation on average.

The `pop()` method is more complex. Since we need to pop the most frequent element, and in case of a tie, the one closest to the top, we must first determine the frequencies of all elements. We can do this by iterating through the entire list and using a `HashMap` to store counts. While doing so, we can also keep track of the maximum frequency seen so far. After this initial `O(N)` scan, we know the `maxFreq`. Now, to respect the tie-breaking rule (closest to the top), we must scan the list again, but this time from the end towards the beginning. The first element we find whose frequency matches `maxFreq` is our target. We then remove it from the list and return it. The removal from an `ArrayList` can also take `O(N)` time, making the overall `pop` operation quite slow.

```java
class FreqStack {
    List<Integer> stack;

    public FreqStack() {
        stack = new ArrayList<>();
    }

    public void push(int val) {
        stack.add(val);
    }

    public int pop() {
        if (stack.isEmpty()) {
            return -1; // Or throw an exception
        }

        Map<Integer, Integer> freqMap = new HashMap<>();
        int maxFreq = 0;
        for (int val : stack) {
            int newFreq = freqMap.getOrDefault(val, 0) + 1;
            freqMap.put(val, newFreq);
            maxFreq = Math.max(maxFreq, newFreq);
        }

        int valToPop = -1;
        int indexToPop = -1;
        for (int i = stack.size() - 1; i >= 0; i--) {
            int currentVal = stack.get(i);
            if (freqMap.get(currentVal) == maxFreq) {
                valToPop = currentVal;
                indexToPop = i;
                break;
            }
        }

        stack.remove(indexToPop);
        return valToPop;
    }
}
```
### Algorithm
- **Data Structure**: Use a single `List` (like `ArrayList` in Java) to store the elements in the order they are pushed.
- **`push(val)` operation**:
  - Simply append the new element `val` to the end of the list.
- **`pop()` operation**:
  1. Create a temporary `HashMap` to calculate the frequency of every element currently in the list.
  2. Iterate through the list to populate the frequency map and find the maximum frequency (`maxFreq`).
  3. Iterate through the list *backwards*, from the last element to the first.
  4. For each element, check its frequency in the map. The first element encountered that has a frequency equal to `maxFreq` is the one to be popped.
  5. Remove this element from the list by its index.
  6. Return the removed element.

## Optimized Approach using Map of Stacks
This highly efficient approach achieves constant time complexity for both `push` and `pop` operations by using a clever combination of data structures. It avoids the costly re-computation of frequencies by maintaining them incrementally. The core idea is to group elements by their frequency. For each frequency level, we maintain a stack of elements that have that frequency. This allows us to instantly access the most frequent elements and, thanks to the stack property, find the one that was added most recently.
**Time:** - `push(val)`: O(1) average time.
- `pop()`: O(1) average time.
All operations involve hash map and stack manipulations, which take constant time on average. · **Space:** O(N), where N is the number of elements pushed to the stack. The `freqMap` can store up to U unique elements (where U <= N), and the `group` map stores N total elements across all its stacks.
**Pros:** Extremely efficient, with average time complexity of O(1) for both `push` and `pop` operations.; Scales well with a large number of operations.
**Cons:** Requires more complex data structures, which can be harder to reason about initially.; Uses more memory due to the overhead of multiple HashMaps and Stack objects compared to a simple list.
### Explanation
To optimize the `pop` operation, we need to avoid the linear scans. We can achieve this by maintaining more state. We use two `HashMap`s and an integer variable:

1.  `freqMap`: A `HashMap<Integer, Integer>` that maps each element to its current frequency. This allows `O(1)` lookup of any element's frequency.
2.  `group`: A `HashMap<Integer, Stack<Integer>>`. This is the key data structure. It maps a frequency to a `Stack` of elements that have that frequency. For example, `group.get(3)` would give us a stack of all numbers that currently appear 3 times. The stack ensures that elements that reached this frequency later are on top.
3.  `maxFreq`: An integer that tracks the current maximum frequency among all elements. This avoids the need to search for it.

**How it works:**
- **`push(val)`**: We find the new frequency of `val` and update `freqMap`. We update `maxFreq` if necessary. Then, we push `val` onto the stack corresponding to its new frequency in the `group` map. All these are `O(1)` operations.
- **`pop()`**: We know the element to pop must have a frequency of `maxFreq`. We use `group.get(maxFreq)` to get the stack of such elements. The top of this stack is our target because it was the last one to achieve this frequency. We pop it, update its frequency in `freqMap`, and if the stack for `maxFreq` becomes empty, we decrement `maxFreq`. This is also an `O(1)` operation.

```java
class FreqStack {
    // Map to store frequency of each element
    Map<Integer, Integer> freqMap;
    // Map to group elements by their frequency. Each frequency maps to a stack.
    Map<Integer, Stack<Integer>> group;
    // Variable to track the maximum frequency encountered so far
    int maxFreq;

    public FreqStack() {
        freqMap = new HashMap<>();
        group = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int val) {
        // Get current frequency and increment it
        int freq = freqMap.getOrDefault(val, 0) + 1;
        // Update the frequency map
        freqMap.put(val, freq);

        // Update the max frequency
        maxFreq = Math.max(maxFreq, freq);

        // Add the element to the stack corresponding to its new frequency
        group.computeIfAbsent(freq, k -> new Stack<>()).push(val);
    }

    public int pop() {
        // Get the stack of elements with the maximum frequency
        Stack<Integer> topStack = group.get(maxFreq);
        // Pop the most recently added element from this stack
        int val = topStack.pop();

        // Decrement the frequency of the popped element
        freqMap.put(val, freqMap.get(val) - 1);

        // If the stack for the max frequency becomes empty and there are still elements,
        // it means the new max frequency is one less.
        if (topStack.isEmpty()) {
            maxFreq--;
        }

        return val;
    }
}
```
### Algorithm
- **Data Structures**:
  - `freqMap`: A `HashMap<Integer, Integer>` to store the frequency of each element (`element -> frequency`).
  - `group`: A `HashMap<Integer, Stack<Integer>>` to group elements by their frequency (`frequency -> Stack of elements`).
  - `maxFreq`: An integer to keep track of the current maximum frequency.
- **`push(val)` operation**:
  1. Retrieve the current frequency of `val` from `freqMap`, increment it, and update the map.
  2. Update `maxFreq` to be the maximum of its current value and the new frequency of `val`.
  3. Access the `group` map with the new frequency as the key. Push `val` onto the stack found at that key. If no stack exists, create a new one first.
- **`pop()` operation**:
  1. Get the stack of elements associated with `maxFreq` from the `group` map.
  2. Pop the top element from this stack. This element is the most frequent and was the most recently pushed among all elements with that frequency.
  3. Decrement the frequency of the popped element in `freqMap`.
  4. If the stack for `maxFreq` becomes empty after the pop, it means there are no more elements with that frequency, so decrement `maxFreq`.
  5. Return the popped element.

# Solutions
### Java

```java
class FreqStack { private Map < Integer , Integer > cnt = new HashMap <>(); private Map < Integer , Deque < Integer >> d = new HashMap <>(); private int mx ; public FreqStack () { } public void push ( int val ) { cnt . put ( val , cnt . getOrDefault ( val , 0 ) + 1 ); int t = cnt . get ( val ); d . computeIfAbsent ( t , k -> new ArrayDeque <>()). push ( val ); mx = Math . max ( mx , t ); } public int pop () { int val = d . get ( mx ). pop (); cnt . put ( val , cnt . get ( val ) - 1 ); if ( d . get ( mx ). isEmpty ()) { -- mx ; } return val ; } } /** * Your FreqStack object will be instantiated and called as such: * FreqStack obj = new FreqStack(); * obj.push(val); * int param_2 = obj.pop(); */
```

### CPP

```cpp
class FreqStack { public: FreqStack () { } void push ( int val ) { ++ cnt [ val ]; d [ cnt [ val ]]. push ( val ); mx = max ( mx , cnt [ val ]); } int pop () { int val = d [ mx ]. top (); -- cnt [ val ]; d [ mx ]. pop (); if ( d [ mx ]. empty ()) -- mx ; return val ; } private: unordered_map < int , int > cnt ; unordered_map < int , stack < int >> d ; int mx = 0 ; }; /** * Your FreqStack object will be instantiated and called as such: * FreqStack* obj = new FreqStack(); * obj->push(val); * int param_2 = obj->pop(); */
```

### Python

```python
class FreqStack : def __init__ ( self ): self . cnt = defaultdict ( int ) self . d = defaultdict ( list ) self . mx = 0 def push ( self , val : int ) -> None : self . cnt [ val ] += 1 self . d [ self . cnt [ val ]]. append ( val ) self . mx = max ( self . mx , self . cnt [ val ]) def pop ( self ) -> int : val = self . d [ self . mx ]. pop () self . cnt [ val ] -= 1 if not self . d [ self . mx ]: self . mx -= 1 return val # Your FreqStack object will be instantiated and called as such: # obj = FreqStack() # obj.push(val) # param_2 = obj.pop()
```