Problem Explanation

The goal of this problem is to create a class named FreqStack that simulates a stack-like data structure. FreqStack has two primary functions:

• push(int x): Push an integer x onto the stack.
• pop(): Remove and return the most frequent element in the stack. If there is a tie for the most frequent element, the element found at the top of the stack is removed.

As an example, if the following operations are performed:

push(5), push(7), push(5), push(7), push(4), push(5), pop(), pop(), pop(), pop()

The output would be 5, 7, 5, 4.

It's notable that if multiple elements have the same frequency, then the element closest to the top is removed.

Problem Approach

The solution seems to use a hashmap and a stack. The hashmap count stores the frequency count of every integer pushed into the stack, while, a hashmap of stacks, countToStack, uses frequency as the key and a stack of integers having that frequency as the value.

When pop() is called, it identifies the maximum frequency maxFreq from the count hashmap, and then pops from the corresponding stack in countToStack. If the corresponding stack becomes empty, it reduces maxFreq by one.

Python Solution

1
2python
3class FreqStack:
4
5    def __init__(self):
6        self.freq = collections.Counter()
7        self.m = collections.defaultdict(list)
8        self.maxf = 0
9
10    def push(self, x: int) -> None:
11        freq, m = self.freq, self.m
12        freq[x] += 1
13        self.maxf = max(self.maxf, freq[x])
14        m[freq[x]].append(x)
15
16    def pop(self) -> int:
17        freq, m, maxf = self.freq, self.m, self.maxf
18        x = m[maxf].pop()
19        if not m[maxf]: self.maxf = maxf - 1
20        freq[x] -= 1
21        return x

Java Solution

1
2java
3class FreqStack {
4    HashMap<Integer, Integer> freq = new HashMap<>();
5    HashMap<Integer, Stack<Integer>> group = new HashMap<>();
6    int maxfreq = 0;
7    public void push(int x) {
8        int f = freq.getOrDefault(x, 0) + 1;
9        freq.put(x, f);
10        if (f > maxfreq)
11            maxfreq = f;
12        group.computeIfAbsent(f, z->new Stack()).push(x);
13    }
14    public int pop() {
15        int x = group.get(maxfreq).pop();
16        freq.put(x, freq.get(x) - 1);
17        if (group.get(maxfreq).size() == 0)
18            maxfreq--;
19        return x;
20    }
21}

JavaScript Solution

1
2javascript
3class FreqStack {
4    constructor() {
5        this.freqMap = new Map();
6        this.freqMaxArr = [];
7        this.maxFreq = 0;
8    }
9    push(x) {
10        this.freqMap.has(x)? this.freqMap.set(x, this.freqMap.get(x)+1) : this.freqMap.set(x, 1);
11        const freq = this.freqMap.get(x);
12        if(freq > this.maxFreq) this.maxFreq = freq;
13        if(!this.freqMaxArr[freq]) this.freqMaxArr[freq] = [];
14        this.freqMaxArr[freq].push(x);
15    }
16    pop() {
17        const x = this.freqMaxArr[this.maxFreq].pop();
18        this.freqMap.set(x, this.freqMap.get(x)-1);
19        if(this.freqMaxArr[this.maxFreq].length === 0) this.maxFreq--;
20        return x;
21    }
22};

C++ Solution

1
2cpp
3class FreqStack {
4    unordered_map<int, int> freq;
5    unordered_map<int, stack<int>> m;
6    int maxfreq = 0;
7public:
8    FreqStack() {
9
10    }
11
12    void push(int x) {
13        maxfreq = max(maxfreq, ++freq[x]);
14        m[freq[x]].push(x);
15    }
16
17    int pop() {
18        int top = m[maxfreq].top();
19        m[maxfreq].pop();
20        if (!m[freq[top]--].size()) maxfreq--;
21        return top;
22    }
23};

C# Solution

1
2csharp
3public class FreqStack
4{
5    Dictionary<int, int> freq;
6    Dictionary<int, Stack<int>> group;
7    int maxfreq;        
8    public FreqStack() {
9        freq = new Dictionary<int, int>();
10        group = new Dictionary<int, Stack<int>>();
11        maxfreq = 0;
12    }        
13    public void Push(int x) {
14        if (!freq.ContainsKey(x))
15            freq[x] = 0;
16        freq[x] +=1;
17        if (freq[x] > maxfreq)
18            maxfreq = freq[x];
19        if (!group.ContainsKey(freq[x]))
20            group[freq[x]] = new Stack<int>();
21        group[freq[x]].Push(x);
22    }        
23    public int Pop() {
24        int x = group[maxfreq].Pop();
25        freq[x] -= 1;
26        if (group[maxfreq].Count == 0)
27            maxfreq--;
28        return x;
29    }
30}

Thus, we have provided solutions to the problem in various languages, namely Python, Java, JavaScript, C++, and C#. This exercise is a great example of problems that can be solved using a combination of hashmaps and stacks, one of the preferred methods for simulated problems with state charge.

In this approach, a hash map was utilized to facilitate quick frequency lookups in the class. Here, the use of a stack was favored because it guarantees that elements pushed later are popped first, ensuring compliance with our problem constraints. The C# and C++ versions arguably provide the cleanest implementations, where the syntax of both languages is very well suited to this problem.

Remember, the best solution often depends on the individual problem, the language you're coding in, and your skill level with that language. It's often beneficial to be comfortable with a variety of solutions so you can adapt to any situation.