How do you find the k most frequent elements in a list?
You count how many times each thing appears, and then you take the k biggest counts. There are three ways to do the second part, and they differ in how much they cost.
The first way is to sort the counts and take the first k. That is O of n log n for the time and it is the simplest to write.
The second way is to use a heap that holds k items. That is O of n log k for the time and O of k for the space, and it is the right choice when k is small and the list is big.
The third way is to use the counting sort idea, because the counts are all small whole numbers. You make a list of counters for the possible counts and you work down from the biggest. That is O of n for the time.
the method the time the space
---------------- --------------- ----------
sorting O(n log n) O(n)
a heap O(n log k) O(k)
counting O(n) O(n)
And the counting version is worth knowing about because the counts cannot be bigger than n, so you can use a list of size n plus one and sort by counting instead of by comparing.
from collections import Counter
def top_k_frequent_counting(values, k):
counts = Counter(values)
buckets = [[] for _ in range(len(values) + 1)]
for value, amount in counts.items():
buckets[amount].append(value)
answer = []
for amount in range(len(values), 0, -1):
for value in buckets[amount]:
answer.append(value)
if len(answer) == k:
return answer
return answer
And there is one thing that you have to say out loud in an interview. The question has two parts. Finding the k most frequent values is different from finding the k most common values, because two values can have the same count and then either one of them could be the answer. So you have to say which one you pick when there is a tie.
So the rule to remember is this. Count first, and then take the k biggest counts, and say what you do about ties.
The last question in this topic shows the heap version.