Algorithm
Problem Name: 895. Maximum Frequency Stack
Problem Link: https://leetcode.com/problems/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 integervalonto 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 * 104calls will be made topushandpop. - 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;
}
}
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]
#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
};
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]
#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
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]
#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 readonly IDictionary<int, Stack<int>> frequencyValues;
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;
}
}
}
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]