5 ms·
> This can be done trivially by keeping the best three found so far and scanning the list. That doesnt seem to guarantee correctness. If you dont track all of
by Akronymus 1y ago
> This can be done trivially by keeping the best three found so far and scanning the list.
That doesnt seem to guarantee correctness. If you dont track all of the unique values, at least, you could be throwing away one of the most common values.
The wiki entry seems to be specifically about the smallest, rather than largest values.
- recursive 1y agoWhat? The algorithm is completely symmetrical with respect to smallest or largest, and fully correct and general. I don't understand the problem with unique values. Could you provide a minimal input demonstrating the issue?
- Akronymus 1y agoI cant because I completely misread the wiki article before commenting and have now read it more carefully and realized I was wrong. Specifically I went in thinking about top 3 most common value.
- datadrivenangel 1y agoWith an equality that returns true/false, this guarantees correctness. If there can be 3 best/biggest/smallest values, this technique works.
- senderista 1y agoThe max-heap algorithm alluded to above is correct. You fill it with the first k values scanned, then peek at the max element for each subsequent value. If the current value is smaller than the max element, you evict the max element and insert the new element. This streaming top-k algorithm is ubiquitous in both leetcode interviews and applications. (The standard quickselect top-k algorithm is not useful in the streaming context because it requires random access and in-place mutation.)
- Akronymus 1y agoMy failure was misreading it as most common k rather than max k.
- senderista 1y agoMost 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_elements https://en.wikipedia.org/wiki/Streaming_algorithm#Frequent_e...
- 3np 1y agoWhy 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.
- senderista 1y agoSure, a similar trivial argument applies to the linear-space lower bound for set membership. But these linear lower bounds motivate the search for approximate techniques with sublinear lower bounds (although bloom filters or fingerprint tables are not actually sublinear).
- eru 1y agoThe algorithms on the Wikipedia page quoted actually solve a different problem. And they can do that in constant space. So if someone tells you that one item in the stream is repeated so often that it occurs at least p% of the time (say 10%), then these algorithms can find such an element. But eg if they are multiple elements that occur more than p% of the time, they are not guaranteed to give you the one that occurs the most often. Nor are they guaranteed to give you any meaningful output, if the assumption is violated and no element occurs at least p% of the time.
- eru 1y agoWhat you are quoting solves a very different problem. It doesn't give you the most common k (in general).