Intuition
Count first, then select. A size-k min-heap over (frequency, value) picks the k biggest counts in O(n log k) — or bucket-by-frequency does it in O(n) flat, since a frequency can't exceed n.
Two independent steps hide in this one line: counting, then selecting. Counting is a hash map; selecting the top k from n counts is the heap question again. Recognising that "top k" never requires a full sort is the reusable part — you only need the k best, and a heap delivers that in O(n log k).
Approach
Count with a hash map
One pass builds value → frequency. All selection happens on the (much smaller) distinct set.
Heap-select the top k
Stream (freq, val) pairs through a size-k min-heap exactly like Kth Largest — smallest frequency guards the gate.
Bucket alternative
Index buckets by frequency 1..n, drop each value into bucket[freq], then read buckets from the top until k values are collected — O(n).
Solution & live demo
Common pitfalls
Sorting the whole frequency map
return [v for v, _ in freq.most_common()[:k]]
return [v for _, v in heapq.nlargest(k, ((f, v) for v, f in freq.items()))]
Fully ordering every distinct value is O(m log m) to answer a question about only k of them. nlargest keeps a heap of size k, so it's O(m log k) — and when k is small, that's the difference the interviewer is asking about.
Heapifying on the value rather than the frequency
heapq.nlargest(k, freq.items())
heapq.nlargest(k, ((f, v) for v, f in freq.items()))
freq.items() yields (value, frequency), so comparisons run on the value and you get the k largest numbers rather than the k most common. The sort key has to sit first in the tuple, which is why the pair is flipped.
Assuming ties break in a particular order
# expecting [1, 2] specifically when both appear twice
# any order among equally-frequent values is accepted
When several values share a frequency the problem accepts any of them, and the heap's internal ordering decides arbitrarily. Writing a test that pins one exact permutation makes a correct solution look broken.
Edge cases
Every value is returned; order among them is free.
Problem guarantees a unique answer set — ties never straddle the cut.