Maximum Frequency Stack - Video Solutions
Maximum Frequency Stack - Leetcode 895 - Python
Maximum Frequency Stack - Video Solution
Watch 10 video solutions for Maximum Frequency Stack, a hard level problem involving Hash Table, Stack, Design. This walkthrough by NeetCode has 41,322 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 integervalonto the top of the stack.int pop()removes and returns the most frequent element in the stack.- If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.
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 <= 109- At most
2 * 104calls will be made topushandpop. - It is guaranteed that there will be at least one element in the stack before calling
pop.
Approach Overview
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.
Complexity Analysis
| 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. |