DSA problem
Maximum Frequency Stack
Design a stack-like data structure that pops the most frequent element. If there is a tie for the most frequent element, the element closest to the top of the stack is removed and returned.
The naive approach scans the whole stack on every pop to find the most frequent value — O(n) per call. We can do far better by precomputing frequency information as elements are pushed.
The key insight: when x is pushed and its new frequency is f, we treat that occurrence as belonging to "the f-th copy of x". We can keep a separate stack for every frequency level. The f-th occurrence of any value goes onto stack groups[f]. To pop the most frequent element, we just pop from groups[maxFreq] — and tie-breaking is automatic because each groups[f] is itself a stack, so the most recently pushed element with frequency f is on top.
The implementation needs three pieces: a hash map freq from value to current frequency, an array (or map) groups from frequency to a stack of values, and an integer maxFreq tracking the largest non-empty bucket. push(x): bump freq[x], append x to groups[freq[x]], update maxFreq. pop: pop from groups[maxFreq], decrement that value's frequency, and if groups[maxFreq] is now empty, decrement maxFreq. Both operations are amortized O(1).
Examples
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"]
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]][null,null,null,null,null,null,null,5,7,5,4]["FreqStack","push","push","pop","pop"]
[[],[1],[2],[],[]][null,null,null,2,1]["FreqStack","push","push","push","pop","pop","pop"]
[[],[9],[9],[9],[],[],[]][null,null,null,null,9,9,9]Constraints
- 0 <= val <= 10^9
- At most 2 * 10^4 calls will be made to push and pop.
- It is guaranteed that there will be at least one element in the stack before calling pop.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.