Maximum Frequency Stack
Design FreqStackpush(val)pop()
Example 1
Output: 5, 7, 5, 4
Explanation: 5 appears 3 times, so it goes first. Then 5 and 7 both appear twice, and 7 was pushed more recently. Then 5 (twice) beats 4 and 7 (once). Then 4, 5 and 7 all appear once, and 4 is the most recent.
How to Think About It
Step 1: Two things decide the order
First the frequency, then recency. A priority queue ordered by (frequency, push time) works in O(log n) per call. There is an O(1) way.
Step 2: One stack per frequency level
When a value is pushed for the f-th time, push it onto the stack for level f. So a value that has been pushed 3 times appears on the stacks for levels 1, 2 and 3, once each.
- The highest level holds exactly the values with the maximum frequency.
- Inside a level, the top is the one that reached that frequency most recently, which is the one pushed most recently.
Step 3: pop
Pop from the highest level, lower that value's count by one, and drop the level if it became empty. The value's copy on the level below stays, which is right: its frequency is now one less.
Walkthrough
After pushing 5, 7, 5, 7, 4, 5 the levels are (bottom to top):
| Step | Level 1 | Level 2 | Level 3 | Returns |
|---|---|---|---|---|
| after the pushes | 5, 7, 4 | 5, 7 | 5 | |
| pop() | 5, 7, 4 | 5, 7 | (removed) | 5 |
| pop() | 5, 7, 4 | 5 | 7 | |
| pop() | 5, 7, 4 | (removed) | 5 | |
| pop() | 5, 7 | 4 |
Java Solution
The class files each pushed value under the frequency it reaches, so the most frequent and most recent value is always on top of the last group.
: it increments the count and returns the new valuefreq.merge(val, 1, Integer::sum) in one call.f- Groups by level:
holds the values that reached frequencygroups.get(f - 1) . A value pushed three times sits in groups 1, 2 and 3, which is how it can be popped three times.f - Ties: inside a group the newest value is on top, so after 5 is popped the first time, 7 beats the older 5 at frequency 2.
- Removing an empty group: when the top group empties, it is removed, so
stays equal to the current maximum frequency.groups.size()
A common mistake is forgetting freq.merge(val, -1, Integer::sum)poppush(5), push(5), pop(), push(5)groups.get(2)IndexOutOfBoundsException
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class FreqStack {
private final Map<Integer, Integer> freq = new HashMap<>();
// groups.get(f - 1): values in the order they reached frequency f
private final List<Deque<Integer>> groups = new ArrayList<>();
public void push(int val) {
int f = freq.merge(val, 1, Integer::sum);
if (f > groups.size()) {
groups.add(new ArrayDeque<>());
}
groups.get(f - 1).push(val);
}
public int pop() {
Deque<Integer> top = groups.get(groups.size() - 1); // highest frequency
int val = top.pop(); // most recent among them
if (top.isEmpty()) {
groups.remove(groups.size() - 1);
}
freq.merge(val, -1, Integer::sum);
return val;
}
}
The original implementation,
Complexity
- Time: O(1) per push and pop. Each call does one
merge (O(1) on average), one deque push or pop, and at most one add or remove at the end of theHashMap .ArrayList - Space: O(n) over all levels: each push adds exactly one entry to one group, so the groups together hold at most n values, and the map has one count per distinct value.
Grouping items into buckets by frequency is also the idea in