You have a firehose of events — say, ad impression IDs streaming in at 500K/sec — and you need to know which IDs appear more than 1/k of the time. Sorting is O(n log n) and needs all the data in memory. A hash map counting every distinct key blows up when you have billions of unique IDs. Misra-Gries solves this in one pass, using only k-1 counters, and guarantees it finds every true "frequent" item (items appearing more than n/k times).

The algorithm is embarrassingly simple. Keep at most k-1 counters, each tagged with an item:

• If the incoming item matches a tracked counter, increment it.
• If there's a free counter slot, start tracking this item at count 1.
• Otherwise, decrement every counter by 1. Any counter that hits zero is evicted.

That third step is the magic. When a new unknown item arrives and everyone's full, you "cancel" it against one instance of every tracked item. A true majority item — say, one appearing >50% of the time with k=2 — can't be fully cancelled out, because there aren't enough other items to pair with it.

Concrete example. You run a CDN and want to find URLs consuming more than 1% of requests (k=100, so 99 counters). You process 10 billion requests/day. A naive hash-map might track 500M distinct URLs — gigabytes of memory. Misra-Gries uses 99 slots — under 10KB. After one pass, every URL truly above 1% is in your counter set. You then do a second verification pass to get exact counts for the survivors, because Misra-Gries counts underestimate the true frequency (they never overestimate).

The rule of thumb: Misra-Gries with k counters guarantees finding all items with frequency > n/k, using O(k) space and O(1) amortized work per item. Error bound: reported count ≤ true count ≤ reported count + n/k.

Where this shows up in the wild. Redis's TOPK command is built on a Misra-Gries variant. Network switches use it to find "elephant flows" without per-flow state. Databases use it during query planning to spot skewed join keys. The Space-Saving algorithm (which you already know) is a refinement — it evicts the minimum counter instead of decrementing everyone, giving tighter error bounds at the same space cost.

The trap: Don't trust the counts as absolute frequencies. Use Misra-Gries to identify candidates, then verify. And remember it only finds items above the n/k threshold — items just below vanish into the noise.