Maximum Frequency Stack
The key idea
Bucket elements by how many times they have been pushed. Keep a stack of values for each frequency level:
group[f] holds, in push order, every value whose count reached f. Pop always takes the top of group[maxFreq] — that single value is automatically the most frequent, and because each level is itself a stack it is also the most recently pushed among the ties.Problem
Design a stack-like data structure where pop removes and returns the most frequent element. Implement the FreqStack class:
- FreqStack() constructs an empty frequency stack.
- 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. If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.
Constraints
0 <= val <= 10^9- At most
2 * 10^4calls in total topushandpop. - It is guaranteed that there will be at least one element before calling
pop.
Examples
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]
Input: ["FreqStack","push","push","push","pop","pop"]
[[],[5],[7],[5],[],[]]
Output: [null,null,null,null,5,7]
Complexity
Time: O(1) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Design problems
- Binary Search Tree IteratorMEDIUM
- Design Circular QueueMEDIUM
- Design HashMapEASY
- Design HashSetEASY
- Design TwitterMEDIUM
- Detect SquaresMEDIUM
- Encode and Decode StringsMEDIUM
- Implement Queue using StacksEASY
- Implement Stack using QueuesEASY
- Insert Delete GetRandom O(1)MEDIUM
- LFU CacheHARD
- LRU CacheMEDIUM