Misra-Gries Heavy Hitters Algorithm
Problem statement
You are processing a stream of $n$ items, where each item is one of many possible keys. A key is called a heavy hitter if it appears more than $n/k$ times in the stream.
Design a single-pass streaming algorithm (Misra-Gries) that uses only $k - 1$ counters and returns a set of candidate keys such that:
- Every true heavy hitter is in the candidate set (no false negatives).
- The candidate set contains at most $k - 1$ keys (so there may be false positives).
Implement the function:
def misra_gries(stream, k):
...
Apply the Misra-Gries counter rule in one pass:
- if
xalready has a counter, increment it; - else if fewer than
k - 1counters are in use, givexa counter set to 1; - else decrement every counter by 1 and drop any that reach 0 (do not insert
x).
Return the surviving candidate keys as a list sorted in ascending order.
Target: $O(n)$ time, $O(k)$ space.
Example
misra_gries([1, 2, 3, 4, 5], 3) -> [4, 5]
With k = 3 there are only k - 1 = 2 counters. Every element is distinct, so the two slots fill with 1 and 2 and only 3 triggers a decrement; 4 and 5 then take the freed slots. Tracing: slots fill with 1 and 2; seeing 3 (a new key, no free slot) decrements both to 0 and empties the dict; then 4 and 5 refill the two now-free slots, so both survive and are returned sorted as [4, 5].
Show hint
If an item with no free slot could cancel against one occurrence of every tracked key, how much damage could such cancellations do to a truly frequent key?
Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.