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.Problem Overview: Design a stack-like data structure where pop() always removes the element with the highest frequency. If multiple elements share the same frequency, return the most recently pushed one. The structure must support efficient push and pop operations while tracking both frequency and recency.
Approach 1: Hash Map with Frequency Stacks (O(1) time, O(n) space)
This approach tracks two things: how often each value appears and which values belong to each frequency level. Maintain a frequency map freq[val] and a second map from frequency to a stack of values. When you push a value, increment its frequency and push it onto the stack for that frequency. Track the current maximum frequency so pop() can directly remove from the corresponding stack.
The key insight: values with the same frequency should behave like a stack to preserve recency order. The highest frequency determines which stack to pop from. This design avoids scanning or sorting because both the frequency lookup and stack operations are constant time. push() and pop() run in O(1) time with O(n) space for stored elements and frequency groups. This solution heavily relies on a hash table for counting and a stack structure to maintain order.
Approach 2: Priority Queue (O(log n) time, O(n) space)
Another option models the problem as a ranking system. Store entries in a max heap ordered by two keys: frequency and insertion time. Each node stores (frequency, timestamp, value). The heap compares frequency first and breaks ties using the timestamp so the most recently inserted element wins.
When pushing a value, update its frequency in a map and push a new heap entry with the updated frequency and a global timestamp. When popping, remove the top element from the heap and decrement its frequency in the map. The heap automatically returns the correct element because the comparator prioritizes higher frequency and more recent insertion.
This approach is easier to reason about if you already use priority queues for ordering problems. However, both push and pop cost O(log n) due to heap operations, making it slower than the frequency stack method.
Recommended for interviews: The hash map with frequency stacks solution is the expected answer. It demonstrates strong understanding of combining counting with grouped stacks to achieve constant-time operations. The priority queue solution is still valid and easier to prototype, but the optimal O(1) design shows deeper data structure insight.
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.
The code uses two dictionaries: 'freq' keeps track of the frequency of each element, and 'group' maintains stacks of elements with the same frequency. The element is pushed into the stack corresponding to its frequency in 'group'. For popping, the element associated with the highest frequency is popped from the appropriate stack.
Python
JavaScript
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.
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.
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.
Time Complexity: O(log n) for both push and pop due to heap operations.
Space Complexity: O(n), with n elements in the stack.
According to the problem description, we need to design a data structure that supports popping out the element with the highest frequency. If multiple elements have the same frequency, the element closest to the top of the stack should be popped out.
We can use a hash table cnt to record the frequency of each element, and a priority queue (max heap) q to maintain the frequency of elements and their corresponding timestamps.
When performing a push operation, we first increment the current timestamp, i.e., ts \gets ts + 1; then we increment the frequency of the element val, i.e., cnt[val] \gets cnt[val] + 1, and finally, we add the triplet (cnt[val], ts, val) to the priority queue q. The time complexity of the push operation is O(log n).
When performing a pop operation, we directly pop an element from the priority queue q. Since the elements in the priority queue q are sorted in descending order of frequency, the popped element is definitely the one with the highest frequency. If multiple elements have the same frequency, the element closest to the top of the stack is popped out, i.e., the element with the largest timestamp is popped out. After popping, we decrement the frequency of the popped element, i.e., cnt[val] \gets cnt[val] - 1. The time complexity of the pop operation is O(log n).
In Solution 1, in order to pop out the required element, we maintained a priority queue and had to operate on it each time, which has a time complexity of O(log n). If we can find the required element in O(1) time, then the time complexity of each operation of the entire data structure can be reduced to O(1).
In fact, we can use a variable mx to record the current maximum frequency, a hash table d to record the list of elements corresponding to each frequency, and as in Solution 1, a hash table cnt to record the frequency of each element.
When performing a push operation, we increment the frequency of the element, i.e., cnt[val] \gets cnt[val] + 1, and then add the element val to the corresponding frequency list in the hash table d, i.e., d[cnt[val]].push(val). If the current element's frequency is greater than mx, then update mx, i.e., mx \gets cnt[val]. The time complexity of the push operation is O(1).
When performing a pop operation, we take the list of elements with frequency mx from the hash table d, pop out the last element val in the list, and then remove val from the hash table d, i.e., d[mx].pop(). Finally, we decrement the frequency of val, i.e., cnt[val] \gets cnt[val] - 1. If the list d[mx] is empty, it means that all elements with the current maximum frequency have been popped out, and we need to decrement mx, i.e., mx \gets mx - 1. The time complexity of the pop operation is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map with Frequency Stacks | Time Complexity: O(1) for both push and pop as it uses hashed or array operations. |
| Approach 2: Priority Queue | Time Complexity: O(log n) for both push and pop due to heap operations. |
| Hash Table + Priority Queue (Max Heap) | — |
| Double Hash Tables | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map with Frequency Stacks | O(1) push, O(1) pop | O(n) | Best general solution. Interview-preferred design with constant-time operations. |
| Priority Queue (Max Heap) | O(log n) push, O(log n) pop | O(n) | Useful when heap ordering logic is easier to implement or when constant-time stack grouping is not obvious. |
Maximum Frequency Stack - Leetcode 895 - Python • NeetCode • 38,909 views views
Watch 9 more video solutions →Practice Maximum Frequency Stack with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor