You've got a firehose of events — search queries, page views, error codes, ad clicks — and someone wants "the top 100 most frequent items." The naive answer is a hash map: count everything, sort, return the top 100. This works until your key space explodes. A billion distinct search queries a day means a billion counters, and sorting them to find 100 is absurd.

The Top-K problem is the interview question everyone gets wrong on the first try. The exact solution is O(N) memory in the number of distinct keys, which is unbounded. The practical solution is to accept approximation.

The heavy hitters insight: in real traffic, distribution is Zipfian. A tiny handful of items dominate, and everything else is noise. You don't need to count the noise accurately — you just need to not lose the giants in it.

The Space-Saving algorithm (Metwally, 2005) exploits this beautifully. Keep exactly K + a few hundred counters. When a new item arrives:

• If it's already tracked, increment its counter.
• If not, find the counter with the minimum count, evict that key, and reassign the slot to the new item with count = min + 1.

That "+1" is the trick: the new item inherits the evicted counter's value as an upper bound on its true count. You never underestimate a heavy hitter, and you can prove the error bound is at most N/m, where m is the number of counters.

Real example: Twitter's trending topics don't use exact counts. With ~500 million tweets per day and millions of hashtags, exact counting is possible but wasteful. Space-Saving with a few thousand counters gets the top 50 trends with error under 0.02% — indistinguishable from truth for a UI showing round numbers.

Rule of thumb: to find the top K items with relative error ε, allocate K/ε counters. Want top 100 with 1% error? Use 10,000 counters. That's ~80KB of memory to track heavy hitters in a stream of any size. Compare to a hash map of a billion keys at ~40 bytes each: 40GB versus 80KB, a 500,000× reduction.

When exact matters: billing, fraud detection, compliance. If you're charging customers based on the count, approximate is malpractice. For dashboards, trending UIs, cache admission policies, and anomaly detection — approximate is not just acceptable, it's the only thing that scales.

Pair Space-Saving with Count-Min Sketch when you need frequency estimates for arbitrary items, not just the top K. Different tools, same philosophy: give up perfection, gain scale.