Watch 10 video solutions for Maximum Frequency Stack, a hard level problem involving Hash Table, Stack, Design. This walkthrough by NeetCode has 38,909 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |