Sponsored
Sponsored
This approach uses a combination of hash maps and stacks. We keep a hash map to track the frequency of each element in the stack. Additionally, we use another hash map, where the key is the frequency and the value is a stack that stores elements with that frequency. This allows us to efficiently retrieve and remove the most frequent element.
Time Complexity: O(1) for both push and pop as it uses hashed or array operations.
Space Complexity: O(n), where n is the number of elements in the stack.
1class FreqStack {
2 constructor() {
3 this.freq = new Map();
4 this.group = new Map();
5 this.maxfreq = 0;
6 }
7
8 push(x) {
9 const f = (this.freq.get(x) || 0) + 1;
10 this.freq.set(x, f);
11 if (f > this.maxfreq) {
12 this.maxfreq = f;
13 }
14 if (!this.group.has(f)) {
15 this.group.set(f, []);
16 }
17 this.group.get(f).push(x);
18 }
19
20 pop() {
21 const x = this.group.get(this.maxfreq).pop();
22 this.freq.set(x, this.freq.get(x) - 1);
23 if (this.group.get(this.maxfreq).length === 0) {
24 this.maxfreq--;
25 }
26 return x;
27 }
28}In this JavaScript solution, we maintain the frequency of each element in a Map and manage stacks of elements keyed by their frequency in a separate Map. The 'push' method increases the frequency of an element and places it in the corresponding stack. In 'pop', the most frequent element is returned and its frequency is decreased.
This approach employs a priority queue (heap) to manage elements based on their frequency and their occurrence order. Each element in the queue is represented as a tuple (negative frequency, order, element) to simulate a max-heap based on frequency, breaking ties using the order of elements.
Time Complexity: O(log n) for both push and pop due to heap operations.
Space Complexity: O(n), with n elements in the stack.
1#include <unordered_map>
2#include <vector>
3#include <queue>
4#include <utility>
5
class FreqStack {
std::unordered_map<int, int> freq;
std::priority_queue<std::pair<int, std::pair<int, int>>> pq;
int indexCounter = 0;
public:
void push(int x) {
int f = ++freq[x];
pq.push({f, {++indexCounter, x}});
}
int pop() {
auto [f, p] = pq.top();
pq.pop();
int x = p.second;
freq[x]--;
return x;
}
};This C++ implementation uses an unordered_map to maintain frequency counts and a priority queue to order elements by frequency and recency. The priority queue ensures that the most frequent, most recent element is always at the top, providing efficient pops.