alt Hacker NewsMost common k is super-interesting because it can't be solved in one pass in constant space!
https://en.wikipedia.org/wiki/Streaming_algorithm#Frequent_e...
Replies
3np • last Tuesday at 6:40 PM
Why is that interesting? Intuitively a worst-case could be a stream of n-1 unique elements out of n with the duplicate at the end, so there is no way around O(n) space. Any element could be the most common so you must keep them all.
➕ show 2 replies
What you are quoting solves a very different problem. It doesn't give you the most common k (in general).