hardStack / QueuePure DSA~40 min
Pop The Most Frequent Recent Item
Design a counter-aware stack. push(x) records x; pop() removes and returns the value that has been pushed most often. Ties go to the value pushed most recently. Both operations must be O(1) amortised.
Problem
Implement a FreqStack supporting push(val) and pop(). pop() removes and returns the most frequent element; if several share the top frequency, return the one closest to the top (most recently pushed among them).
Input
A sequence of push(val) and pop() operations.
Output
The value returned by each pop() call.
Constraints
- 0 ≤ val ≤ 1e9
- At most 2e4 calls total.
- pop() is only called on a non-empty stack.
Examples
Example 1
Input
push(5),push(7),push(5),push(7),push(4),push(5),pop(),pop(),pop(),pop()
Output
5,7,5,4
5 has freq 3 → pop 5; then 5 and 7 tie at freq 2, 7 is more recent → pop 7; then 5 (freq 2) → pop 5; then 4,7 tie at freq 1, 4 more recent → pop 4.
Example 2
Input
push(1),push(1),pop(),pop()
Output
1,1
Both pops return 1.