Maximum Frequency Stack
Hard · Design · Hash Table · Stack · Design · Ordered Set
Problem
Design a stack-like structure whose pop removes the most frequent element rather than simply the top one.
Implement FreqStack:
- FreqStack() creates an empty stack.
- void push(int val) pushes val onto the top.
- int pop() removes and returns the element that currently occurs most often. If several elements tie for the highest count, remove and return the one closest to the top of the stack.
The tests call the class through a list of operation names and a list of their arguments; each call's return value is collected, with None for the constructor and push.
Examples
Input: ops = ["FreqStack","push","push","push","push","pop","pop","pop","pop"], args = [[],[3],[8],[3],[8],[],[],[],[]] Output: [null,null,null,null,null,8,3,8,3]
3 and 8 tie at two each, so the one nearer the top (8) goes first. Then 3 has two copies and leaves, and the two single copies leave top first: 8, then 3.
Input: ops = ["FreqStack","push","push","push","pop","pop"], args = [[],[1],[1],[2],[],[]] Output: [null,null,null,null,1,2]
1 appears twice so it leaves first; then 1 and 2 tie and 2 is nearer the top.
Input: ops = ["FreqStack","push","push","push","push","push","pop","pop","pop"], args = [[],[4],[4],[9],[6],[4],[],[],[]] Output: [null,null,null,null,null,null,4,4,6]
4 has three copies and leaves first even though it is not always on top; then 4 has two and leaves again; then 6, 9 and 4 tie at one, and 6 is nearest the top.
Constraints
- 0 <= val <= 10^9
- At most 2 · 10^4 calls are made to push and pop
- pop is never called on an empty stack
Approaches
- Baseline: recount on every pop — time O(n) per pop, space O(n)
Follow-up
What if ties went to the smallest value instead of the one nearest the top? The same groups work if each group is a min-heap instead of a stack, at O(log n) per call: see the use case "Frequency stack with ties to the smallest value".
Related problems
Start free on Cariara · Coding problems · System design studio
