Coding Interview PatternsMaximum Frequency Stack
HardCustom Data Structures
Maximum Frequency Stack
Explanation & Solution
Description
Design a stack that always pops the most frequently occurring element. If there is a tie, pop the most recently pushed element among the most frequent.
Implement a function that processes an array of operations and an array of arguments:
"FreqStack"— Initializes the frequency stack."push"— Pushesvalonto the stack."pop"— Removes and returns the most frequent element. If there is a tie in frequency, the most recently pushed element is returned.
Input:operations = ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], args = [[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
0
FreqStack
1
push
2
push
3
push
4
push
5
push
6
push
7
pop
8
pop
9
pop
10
pop
Output:[null,null,null,null,null,null,null,5,7,5,4]
0
null
1
null
2
null
3
null
4
null
5
null
6
null
7
5
8
7
9
5
10
4
Explanation: Push 5,7,5,7,4,5. Frequencies: 5→3, 7→2, 4→1. Pop: 5 (most frequent, freq=3). Pop: 7 (tie at freq=2 between 5 and 7; 7 was pushed last). Pop: 5 (freq=2). Pop: 4 (only freq=1 element remaining is 4 or 7; 4 was pushed more recently at that level).
Constraints
0 <= val <= 10^9- At most
2 * 10^4calls topushandpop popis never called on an empty stack
Approach
Custom Data Structures pattern
1. Two Maps + maxFreq
- freq: maps
value → current frequency - group: maps
frequency → stack of values with that frequency(push order preserved) - maxFreq: the current maximum frequency in the stack
2. Implement Push
- Increment the value's frequency in
freq - Update
maxFreqif the new frequency exceeds it - Append the value to
group[newFreq]— this records the push order at each frequency level
3. Implement Pop
- Pop from
group[maxFreq]— this gives the most recently pushed value at the max frequency (LIFO) - If
group[maxFreq]becomes empty, remove it and decrementmaxFreq - Decrement the popped value's frequency in
freq
4. Why Group by Frequency?
- Each value can appear in multiple frequency groups: if
5has been pushed 3 times, it appears ingroup[1],group[2], andgroup[3] - Popping from
group[maxFreq]handles both the frequency and recency tiebreaker automatically
5. The Key Insight
- A value pushed for the k-th time is recorded in
group[k] - When it's popped, it leaves
group[k]but remains ingroup[1]..group[k-1] - This layered structure handles all ties correctly
Key Insight
- The group map acts as a frequency-indexed stack of stacks
- Each level contains elements at exactly that frequency, in push order
Time
O(1) for both push and popSpace
O(n) where n is the total number of pushes