###### Maximum Frequency Stack | February Leetcoding Challenge 2021 | Day 28
Manas Sinha
Developer | Designer

## Maximum Frequency Stack

`PROBLEM  STATEMENT:`
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.

## Explanation

One way to solve this problem is to have a heap that keeps the most frequent element on the top and if the frequency is same, it keeps the element which was pushed last at the top. But in this approach the time complexity to push an element will be O(Logn). Let’s see if we can do better.
Instead of heap, we simply maintain an array of stacks such that the stack at index `i` has all the elements with frequency `i`. We keep track of the maximum `i` and pop the top element from the stack at that index when ever there is any pop operation.
`ALGORITHM: `
• Declare two hash tables, one that keeps track of the frequency of each unique element, other is the array of stacks. And a `max_freq` variable that keeps track of maximum frequency.
• Whenever there is a call for push operation push the element `x` in the stack at position `freq[x] + 1`. This is because `freq[x]` is the frequency of `x` before the current push operation so after this call the frequency of `x` will increase by 1. Also update the `max_freq` variable
• In case of pop, pop the top element of the stack at the index `max_freq` , reduce its frequency in the frequency table by 1 and return it.
• If the stack at index `max_freq` is empty after popping the top element, reduce `max_freq` value by 1.
• Time complexity for push : O(1)
• Time complexity for pop : O(1)
• Space complexity : O(n), since we are using extra hash tables.

## C++

``````class FreqStack {
public:
FreqStack() {
max_freq = 0;
}

void push(int x) {
stacks[++freq[x]].push(x);
max_freq = max(max_freq,freq[x]);
}

int pop() {
int res = stacks[max_freq].top();
stacks[max_freq].pop();
freq[res]--;
if(stacks[max_freq].empty())
max_freq--;
return res;
}

private:
map<int,int> freq;
map<int,stack<int>> stacks;
int max_freq;
};

``````

## PYTHON

``````class FreqStack:

def __init__(self):
self.freq = collections.defaultdict(int)
self.stacks = collections.defaultdict(list)
self.max_freq = 0

def push(self, x: int) -> None:
self.freq[x] += 1
self.stacks[self.freq[x]].append(x)
self.max_freq = max(self.max_freq,self.freq[x])

def pop(self) -> int:
temp = self.stacks[self.max_freq].pop()
self.freq[temp] -= 1

if len(self.stacks[self.max_freq]) == 0:
self.max_freq -= 1
return temp

'''we are using defaultdict instead of normal python dict.
This is to ensure that we don't get a keyError beacause we are trying to access keys
which are not yet present in the dictionary.
defaultdict will assume that the default value of the key not yet present in the dictionary is zero'''``````