Run it
Sorting everything against a heap of size k, at 200,000 items.
And the O(n) version, which removes the log factor without necessarily winning the clock.
Where the log k actually comes from: how little of the input ever enters the heap.
Why the root is the whole trick
A min-heap of size k has a useful property: its root is the weakest member of the best k seen so far. So the question "could this candidate belong in the answer?" is one comparison against the root, and if the answer is no the candidate is discarded without ever entering the heap.
The editor below counts it: with 200,000 items and k = 10, only 136 of them ever touched the heap. The other 199,864 cost one comparison each. That is where the log k comes from — not from clever bookkeeping, but from rejecting almost everything cheaply.
The three answers, and when each is right
Heap of size k — O(n log k). The default answer, and the one to give first. heapq.nlargest(k, ...) is this, already written.
Full sort — O(n log n). Better when k is a large fraction of n, because then log k is log n and the heap is paying overhead for nothing. Also better when n is small enough that constants dominate, which is more often than the complexity suggests: CPython's sort is C and a heap loop is Python.
Bucket sort — O(n). Available because the counts are bounded: a count cannot exceed n, so you can bucket by count and read the buckets from the top with no comparisons at all. It is the answer an interviewer is fishing for when they ask "can you do better than n log k?" — though note what the editor measures: it comes out level with nlargest rather than ahead, because removing a log factor does not beat a C implementation at this size. The complexity win is real; the wall-clock win needs a much larger n or k.
Quickselect, and why it is usually the wrong answer to give
There is an O(n) average-case option: partition around a pivot like quicksort but recurse into one side only, stopping when the pivot lands at position k. It is genuinely O(n) expected and O(n²) worst case, and numpy.partition implements it.
Mentioning it is good; reaching for it first is usually not. It mutates the input, it does not stream, the worst case needs median-of-medians to fix, and the constant factor means it rarely beats nlargest in practice. The strong answer is the heap, with quickselect named as the theoretical improvement.
What the question is testing
Whether you notice that the answer set is bounded. A great many problems say "the best k" and the instinct is to sort everything and take a slice — which computes a total order nobody asked for. Keeping only k candidates and rejecting against the weakest of them is the reusable move, and it reappears in streaming top-n, nearest-neighbour search and leaderboards.
The second thing is whether you ask about ties. "The k most frequent" is ambiguous when counts are equal, and saying so before writing is the difference between a correct answer and a complete one.
What to say out loud
Count with a Counter, then keep a min-heap of size k keyed on the count. For each item, if the heap is short push it; otherwise compare against the root and replace only if it is bigger. That is O(n log k). heapq.nlargest does exactly this. If k is close to n I would just sort, and if the counts are small integers bucket sort is O(n).
Edge cases to raise
Volunteering these is most of what separates a correct answer from a good one.
Ties. "The k most frequent" is ambiguous when counts are equal. Ask, or state the tie-break - and note that the tuple in the heap already picks one for you, probably not the one you meant.
k larger than the number of distinct values. nlargest returns everything; a hand-rolled heap should too, rather than raising.
k = 0. An empty answer, and a loop that assumes the heap is non-empty will index a root that is not there.
The follow-ups interviewers ask
"Can you do better than O(n log k)?" Yes: bucket by count. A count cannot exceed n, so there are at most n+1 buckets and reading them from the top is linear with no comparisons. It is the answer they are fishing for, and the editor shows it coming out level with nlargest in wall-clock terms - the complexity win is real and the constant factor is not.
"What if the data does not fit in memory?" The heap already streams: it holds k items and never needs the rest, so one pass over a file works unchanged. Counting is the part that does not - for that you need a bounded counter such as count-min sketch, and then the top-k is approximate.
"What about quickselect?" O(n) expected by partitioning around a pivot and recursing into one side only. Worth naming; rarely worth choosing. It mutates the input, does not stream, needs median-of-medians to fix the O(n2) worst case, and loses to nlargest on constants.
Common wrong answers
"Sort by count and slice." Correct and O(n log n). Fine as a first answer if you say it is the baseline; wrong as a final answer when k is small.
"Use a max-heap of all the items." Building it is O(n) and popping k times is O(k log n) - which is defensible - but it holds the whole input. The point of the size-k heap is bounded memory.
"Push a tuple of (key, count)." Then the heap orders alphabetically. The count has to come first, and this silently returns a wrong answer rather than failing.
Recap in one screen
- The heap never grows past k - that is what makes each operation log k.
- Most candidates are rejected by one comparison against the root.
- The root is the smallest of the kept values, not the largest.
- Worth trying: Set k equal to the number of distinct values and compare the timings again. The heap loses, which is the honest boundary of the recommendation.
- Worth trying: Break the ties deliberately: make two values share a count and decide whether the answer should be alphabetical. The heap's tuple already decides for you, and probably not the way you intended.