Algorithm

Problem Name: 895. Maximum Frequency Stack

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

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class FreqStack {

private Map frequencyMap;
private Map < Integer, Stack();
this.frequencyGroup = new HashMap<>();
this.maxFrequency = 0;
}

public void push(int val) {
int newFrequency = this.frequencyMap.getOrDefault(val, 0) + 1;
this.frequencyMap.put(val, newFrequency);
this.maxFrequency = Math.max(this.maxFrequency, newFrequency);
this.frequencyGroup.computeIfAbsent(newFrequency, k -> new Stack < >()).push(val);
}

public int pop() {
int val = this.frequencyGroup.get(this.maxFrequency).pop();
this.frequencyMap.put(val, this.frequencyMap.get(val) - 1);
if (this.frequencyGroup.get(this.maxFrequency).isEmpty()) {
this.maxFrequency--;
}
return val;
}
}
``````
Copy The Code &

Input

cmd
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output

cmd
[null, null, null, null, null, null, null, 5, 7, 5, 4]

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const FreqStack = function() {
this.stack = Array.from({length: 10001}, () => [])
this.maxf = 0
this.freq = {}
}

FreqStack.prototype.push = function(x) {
if(!this.freq[x]) this.freq[x] = 0
this.freq[x]++
if(this.freq[x] > this.maxf) this.maxf = this.freq[x]
this.stack[this.freq[x]].push(x)
};

FreqStack.prototype.pop = function() {
let res = this.stack[this.maxf].pop()
if(this.stack[this.maxf].length === 0) this.maxf--
this.freq[res]--
return res
};
``````
Copy The Code &

Input

cmd
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output

cmd
[null, null, null, null, null, null, null, 5, 7, 5, 4]

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class FreqStack:

def __init__(self):
self.stacks = collections.defaultdict(list)
self.freq = collections.Counter()
self.maxFreq = 0

def push(self, x):
self.freq[x] += 1
self.maxFreq = max(self.maxFreq, self.freq[x])
self.stacks[self.freq[x]].append(x)

def pop(self):
num = self.stacks[self.maxFreq].pop()
self.freq[num] -= 1
if not self.stacks[self.maxFreq]: self.maxFreq -= 1
return num
``````
Copy The Code &

Input

cmd
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output

cmd
[null, null, null, null, null, null, null, 5, 7, 5, 4]

#4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0895_MaximumFrequencyStack
{
private readonly IDictionary < int, int> frequencyMap;
private int maxFrequency;

public _0895_MaximumFrequencyStack()
{
frequencyMap = new Dictionary < int, int>();
frequencyValues = new Dictionary<int, Stack<int>>();
maxFrequency = 0;
}

public void Push(int x)
{
if (!frequencyMap.ContainsKey(x))
frequencyMap[x] = 0;
frequencyMap[x] += 1;

if (frequencyMap[x] > maxFrequency)
maxFrequency = frequencyMap[x];

if (!frequencyValues.ContainsKey(frequencyMap[x]))
frequencyValues[frequencyMap[x]] = new Stack < int>();
frequencyValues[frequencyMap[x]].Push(x);
}

public int Pop()
{
var result = frequencyValues[maxFrequency].Pop();

frequencyMap[result] -= 1;
if (frequencyValues[maxFrequency].Count == 0)
maxFrequency--;

return result;
}
}
}
``````
Copy The Code &

Input

cmd
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"] [[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output

cmd
[null, null, null, null, null, null, null, 5, 7, 5, 4]