# Maximum Frequency Stack Leetcode Solution

Difficulty Level Hard
Design HashMap Ordered Set StackViews 1433

## Problem Statement

The Maximum Frequency Stack LeetCode Solution – “Maximum Frequency Stack” asks you to design a frequency stack in which whenever we pop an element from the stack, it should return the most frequent element present in 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:

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

Explanation:

• Initialize the Empty Stack.
• After performing 6 times push operations, the elements of the stack are: [5, 7, 5, 7, 4, 5].
• The pop operation will yield the most frequent element present in the stack which is 5. Stack elements are: [5, 7, 5, 7, 4].
• The pop operation will yield the most frequent element present in the stack which is 7. Stack elements are: [5, 7, 5, 4].
• The pop operation will yield the most frequent element present in the stack which is 5. Stack elements are: [5, 7, 4].
• The pop operation will yield the most frequent element present in the stack which is 4. Stack elements are: [5, 7].

## Approach

### Idea:

1. The main idea to solve this problem is to use Hashing.
2. Maintain a global variable maximum frequency which will keep track of the maximum frequency found so far.
3. We’ll maintain a frequency table to store frequencies.
4. Maintain a stack of elements corresponding to each distinct frequency.
5. For each Push Operation:
1. We’ll increment the frequency of the pushed element.
2. We’ll update the maximum frequency if possible.
3. Also, insert the element into a stack of elements corresponding to the current frequency.
6. For each Pop Operation:
1. We’ll pop out the maximum frequency element.
2. Also, pop out the element from the stack of frequencies.
3. Decrement the frequency of the element and return the popped element.

## Code

### Maximum Frequency Stack Leetcode C++ Solution:

```class FreqStack {
public:
int maxfreq;
unordered_map<int,int> freq;
unordered_map<int,stack<int>> mp;
void push(int val) {
freq[val]++;
mp[freq[val]].push(val);
maxfreq = max(maxfreq,freq[val]);
}
int pop() {
int val = mp[maxfreq].top();
mp[maxfreq].pop();
freq[val]--;
if(mp[maxfreq].empty()){
maxfreq--;
}
return val;
}
};```

### Maximum Frequency Stack Leetcode Java Solution:

```class FreqStack {
int maxfreq;
HashMap<Integer, Integer> freq = new HashMap<>();
HashMap<Integer, Stack<Integer>> mp = new HashMap<>();
public void push(int val) {
int curr = freq.getOrDefault(val,0) + 1;
freq.put(val,curr);
maxfreq = Math.max(maxfreq,curr);
if(!mp.containsKey(curr)){
mp.put(curr,new Stack<Integer>());
}
}
public int pop() {
int val = mp.get(maxfreq).pop();
freq.put(val,maxfreq-1);
if(mp.get(maxfreq).size()==0){
maxfreq--;
}
return val;
}
}```

## Complexity Analysis for Maximum Frequency Stack Leetcode Solution

### Time Complexity

The time complexity of the above code is O(1) if we use a good hash function that performs insertion and deletion operation in O(1) time average.

### Space Complexity

The space complexity of the above code is O(N), N = maximum number of calls made to push function. We’re using a hashmap to keep integers and in the worst case, all the elements will be distinct which will take O(N) space to store the frequency of such elements.

Translate »