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.
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 <= 1092 * 104 calls will be made to push and pop.pop.The key challenge in #895 Maximum Frequency Stack is to design a stack-like data structure where the element with the highest frequency is removed first. If multiple elements share the same frequency, the most recently pushed element should be popped. A useful strategy is to combine a hash table with multiple stacks organized by frequency.
Maintain a frequency map that tracks how many times each value appears. At the same time, maintain another structure that groups elements by their current frequency (for example, freq → stack of values). Whenever a value is pushed, update its frequency and place it in the stack corresponding to that frequency. Track the current maxFreq so the pop operation can directly retrieve the most frequent element.
This design ensures that both push and pop operations run efficiently because each operation updates or accesses only a few hash map entries and stacks. The result is a highly optimized solution suitable for interview-level system design questions.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Frequency Stacks | Push: O(1), Pop: O(1) | O(n) |
NeetCode
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;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is a common design-style interview question that tests understanding of hash maps, stacks, and efficient data structure design. Variants of this problem have appeared in interviews at major tech companies.
A combination of a hash table and stacks works best. The hash table tracks element frequencies, while stacks grouped by frequency preserve the order of insertion for elements with the same frequency.
The optimal approach uses a hash map to track the frequency of each value and another map that groups values by their frequency using stacks. By maintaining the current maximum frequency, both push and pop operations can be performed in constant time.
Tracking the maximum frequency allows the pop operation to immediately access the stack containing the most frequent elements. This avoids scanning all elements and ensures the operation runs in O(1) time.
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.