Top K Frequent Elements: Heap vs Quickselect vs Bucket Sort

You have counted the frequencies into a hash map. Thirty seconds later the interviewer asks the question the whole exercise was built around: "Can you do better than O(n log n)?" That follow-up is the real content of Top K Frequent Elements, and it has three acceptable answers — a size-k min-heap at O(n log k), quickselect at average O(n), and bucket sort at guaranteed O(n). Which one the interviewer wants depends on constraints they may not state out loud. This guide covers all three, grounded in the questions where companies actually asked them.

Key Takeaways

• The hash-map counting pass is identical in every solution. Interviews are decided by the selection step that follows it, so spend your explanation time there.
• Default to a min-heap capped at size k: O(n log k) time, O(k) extra space beyond the counts, and it still works when the data is a stream. Say all three of those properties out loud.
• Bucket sort reaches O(n), but only because a frequency is an integer between 1 and n. The moment the ranking key is a distance or a score, buckets stop applying. Say so before the interviewer asks.
• Quickselect averages O(n) but degrades to O(n²); if you propose it, name the worst case and the random-pivot mitigation unprompted, or the follow-up will do it for you.
• Tie-breaking rules ("if two values tie, return the smaller") are not decoration. They test whether you can build a comparator, and they show up as warm-ups at Bytedance and Squarepoint.

The counting pass is settled; the selection step is the interview

Asked at Google — Return the Most Frequent Values in an Array A phone screen opened with the canonical version: given a non-empty integer array, return the k elements that appear most often. Once the candidate had a working solution, the interviewer pushed on two follow-ups: whether the time complexity could beat O(n log n), and how to reduce the space footprint.

Every correct solution starts the same way: one pass over the array, incrementing counts in a hash map. That pass is O(n) time and O(u) space, where u is the number of distinct values. Nobody fails here.

What happens next is the actual question. You now hold u (value, count) pairs and need the k pairs with the largest counts. The lazy move is to sort all the pairs by count and take the first k: O(u log u), which for an array of all-distinct values is O(n log n). It works. It is also precisely the answer the Google follow-up is designed to move you past.

The three answers that survive the follow-up:

1. Size-k min-heap — O(n log k). The workhorse. Handles streams, tiny memory footprint for the selection itself.
2. Bucket sort — O(n). Exploits the fact that a count is an integer no larger than n.
3. Quickselect — average O(n), worst O(n²). In-place partitioning over the pair array.

The interview signal is not knowing one of these. It is knowing which one to reach for under the constraints in front of you, and saying why the others fit worse. The sections below take each in turn, using the question where a company actually demanded it.

The size-k min-heap is the default, and O(n log k) is the number to say

Asked at Amazon — Find Most Frequent Values A single-round interview: after a behavioral question about a challenging project, the candidate got a most-frequent-values problem, solved it brute force, and was then told to rewrite it with a heap. Time expired mid-rewrite. The heap version was not optional polish; it was the graded part.

The Amazon report is worth sitting with. The brute-force solution worked, and the interviewer still required the heap rewrite. At companies that calibrate on LeetCode 347, the heap is treated as the baseline competent answer, and running out of time while producing it reads as unfamiliarity with the pattern.

The trick that makes the heap efficient is inverting your instinct. You want the k largest counts, so a max-heap feels natural: push everything, pop k times. That costs O(u) to heapify plus O(k log u) for the pops, which is fine and worth mentioning as an alternative, but it holds all u pairs in the heap.

The tighter version keeps a min-heap of size k. The heap's top is always the weakest of your current top k, which is exactly the element you would evict. Anything that cannot beat the weakest member cannot belong.

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)              # O(n) time, O(u) space

    heap = []                           # min-heap of (freq, value), size <= k
    for value, freq in counts.items():  # u iterations
        heapq.heappush(heap, (freq, value))   # O(log k)
        if len(heap) > k:
            heapq.heappop(heap)         # evict the least frequent survivor

    return [value for freq, value in heap]

Trace it on nums = [1, 1, 1, 2, 2, 3], k = 2. Counts are {1: 3, 2: 2, 3: 1}. Push (3, 1); push (2, 2); push (1, 3), size hits 3, pop the top, which is (1, 3), the smallest count. The heap holds (2, 2) and (3, 1), so the answer is {1, 2}. Correct.

Complexity, stated precisely: counting is O(n); the heap pass is O(u log k), and since u ≤ n, the total is O(n log k). Extra space is O(u) for the counts plus O(k) for the heap. Interviewers accept the looser "O(n log k)" phrasing, but distinguishing u from n is a cheap way to sound like you have thought about the input, and it matters when the array is a million copies of ten values.

Two implementation details that come up:

• Python compares tuples element-wise, so when two counts tie, heappush falls through to comparing the values. For integers that silently works; for objects with no ordering it throws. Push (freq, i, value) with a counter index if the values are not comparable.
• heapq.nlargest(k, counts, key=counts.get) is a one-liner that does the same thing. Reasonable interviewers allow it after you have shown you know what it does internally. Leading with it is a gamble.

If the heap itself is shaky ground — sift-up versus sift-down, why insertion is O(log n) — that is covered in the heap data structure guide, which also covers when a heap is the wrong tool. This article assumes the heap and focuses on the selection pattern around it.

The eviction loop generalizes far beyond frequencies, which is why it is worth having as muscle memory:

The if len(heap) > k: pop version and the if new > top: pop, push version are equivalent in outcome up to tie handling (push-then-pop can evict an incumbent that ties the newcomer, while comparing strictly-greater keeps it). The compare-first version does fewer heap operations when most elements lose, which is the common case when k is small.

Bucket sort reaches O(n) because a frequency is an integer bounded by n

Asked at Roblox — Find the Most Frequent Log Call An MLE phone screen asked the candidate to find the most frequently occurring call in a log, followed by a few extension questions the report calls easy without describing. The base task is the counting-plus-selection shape this whole page is about, wearing production clothes.

The pressure toward linear time does not usually come from the base question; it comes from follow-ups like Google's "can you beat O(n log n)?" Here is the observation that answers it: an element's frequency is a whole number between 1 and n. There are only n possible frequency values. So instead of comparing counts against each other (which is what heaps and sorts do, and what forces the log factor), you can use the count as an array index.

Build an array of n+1 buckets. Bucket i holds every value that occurred exactly i times. Then walk the buckets from index n downward, collecting values until you have k.

def top_k_frequent_bucket(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]  # index = frequency
    for value, freq in counts.items():
        buckets[freq].append(value)

    result = []
    for freq in range(len(buckets) - 1, 0, -1):   # high freq -> low
        for value in buckets[freq]:
            result.append(value)
            if len(result) == k:
                return result
    return result

Same trace, [1, 1, 1, 2, 2, 3], k = 2: bucket 3 gets [1], bucket 2 gets [2], bucket 1 gets [3]. Walking down from 6: bucket 3 yields 1, bucket 2 yields 2, length hits k, return [1, 2]. Every step (count, scatter into buckets, one downward walk) is O(n). Space is O(n) for the bucket array even when few buckets are occupied.

Now the part generic write-ups omit: when bucket sort does not apply. The technique works because the ranking key is a small, dense integer range. Change the key and it collapses:

• K closest points to the origin: the key is a squared distance — unbounded, not dense. No bucket array.
• Kth largest element in an array (raw values, not frequencies): values can span the full 64-bit range. Bucketing them is counting sort with a prohibitive range.
• Streaming input: buckets need the final counts before the downward walk. A stream never gives you "final".

Saying "bucket sort, because the key here is a count bounded by n — it wouldn't work for k-closest-points" is the single sentence in this topic that most reliably separates pattern-matchers from engineers. Interviewers notice the unprompted boundary.

Quickselect averages O(n), and "average" is the word you must say

Asked at Meta — Find Kth Largest and Tree Ancestors A technical phone screen paired kth-largest-in-an-array with a tree ancestor problem, then pushed variants on both: what changes if the tree is a BST, what if nodes carry parent pointers, what if the structure is too large for memory. The candidate had optimal solutions ready and still hit failing edge cases on the interviewer's tests before passing.

Kth-largest (LeetCode 215) is quickselect's natural habitat, and it is the problem this Meta phone screen opened with. The frequency version is the same algorithm applied to the (value, count) pair array: partition pairs by count, recurse into one side only.

The mechanics, briefly: pick a pivot, partition the array so everything with a larger count sits left of the pivot's final position. If the pivot lands at index k, the first k entries are your top k (unordered). If it lands past k, recurse left; otherwise recurse right with a reduced k. Because you only ever recurse into one side, the expected work is u + u/2 + u/4 + ... = O(u). Add the counting pass and the average total is O(n).

What you must volunteer, before being asked:

• Worst case is O(u²). Adversarial or already-sorted pivot sequences make every partition remove one element. Random pivot selection makes the worst case vanishingly unlikely; median-of-medians makes O(u) a hard guarantee at the cost of a constant factor nobody implements in 45 minutes. Name both, implement random.
• It needs the pairs in an array, and it mutates them. The hash map cannot be partitioned in place; materializing the (value, count) pairs costs O(u) space beyond the counts, and if the caller needs that list intact afterward, copying costs another O(u).
• It does not stream. Partitioning needs the whole array resident.
• Output is unordered. The k survivors are not sorted by count. If the interviewer wants them ranked, that is an extra O(k log k), which is worth stating rather than hiding.

The Meta report shows the practical risk: both problems were familiar to the candidate, and the interviewer's test cases still failed at first. Quickselect's partition boundary is where the off-by-ones live. If you choose it, budget five minutes to hand-trace a 4-element array before declaring victory; the heap has no comparable trap, which is a legitimate reason to prefer it under time pressure even though its complexity is worse on paper.

Which one do you reach for?

When n is huge and k is tiny, the size-k heap stops being one option among three

Asked at Asana — Find the K Closest Points to the Origin In an hour-long onsite coding round, the candidate had to return the k points closest to the origin from n points in the plane, with the interviewer emphasizing that n is much larger than k. A priority queue capped at size k settled it.

The "n >> k" hint is an instruction, not trivia. It rules out two of the three approaches:

• Bucket sort is out immediately — the ranking key is a squared distance, not a bounded integer.
• Quickselect needs all n points in memory to partition. If n is "much larger" because the points arrive from a file, a network feed, or a generator, there is no array to partition.

The size-k max-heap (max, this time: you evict the farthest of your current k closest) processes each point in O(log k) and holds exactly k points at any moment. For n = 10⁸ and k = 10, that is a heap of ten entries against a dataset you never fully materialize. And once the heap is warm, most points fail the compare-against-top check and cost O(1) each; the O(log k) replacement only runs when a point actually improves the answer.

This is the same eviction loop from the frequency problem with the key swapped from count to -distance². Two notes that earn points:

• Compare squared distances. x² + y² preserves order and avoids sqrt, which is both slower and a source of floating-point tie ambiguity.
• If the interviewer extends to "the points arrive continuously and someone can query the current top k at any time," the heap is already the answer. Nothing about the loop changes, and neither alternative can say that.

The same shape shows up in production-flavored questions: most frequent API call in a rolling log window, top spenders in a transaction feed, hottest keys in a cache. Interviewers who ask questions like Microsoft's Retain Top K Elements (keep only the k largest values in a list; linked in the practice section below) are checking whether you reach for the bounded heap without being told n is large.

Top-k across sorted inputs is a k-way merge, not a re-sort

Asked at eBay — Return the K Smallest Values from Sorted Arrays Given several arrays that are each already sorted, return the k smallest elements overall. The interviewer explicitly rejected the solution that dumps every element into one min-heap and pops k times, and asked for an approach that maintains a pointer into each array instead.

This variant punishes the reflex the previous sections built. Dumping all N elements (N = total across arrays) into a heap and popping k times is not even as slow as it looks: with a linear-time heapify it costs O(N + k log N), and only the push-one-at-a-time version is O(N log N). The interviewer's objection survives the better accounting anyway. Any approach that touches all N elements is Ω(N), and the one thing you were given, that the inputs are already sorted, is exactly the structure that lets you stay sublinear in N.

The accepted shape is a k-way merge. Keep one cursor per array. Seed a min-heap with each array's head: m entries for m arrays, not N. Pop the global minimum, advance that array's cursor, push its next element. Each pop-push is O(log m), and you stop after k pops: O(k log m) total, independent of N. For 20 arrays of a million elements each and k = 100, that is a few hundred heap operations instead of twenty million touches.

The heap here plays a different role than in the frequency problem. There it was a filter holding the best k seen so far; here it is a merge frontier holding one candidate per source. Same data structure, different invariant. Being able to articulate that difference is what the question is screening for.

The two-array special case was asked at Glean as a straightforward question, and it escalates beyond what that interview required: two sorted arrays can be merged to the kth element in O(k), and the classic hard version (general knowledge, not something the Glean interviewer pushed) reaches O(log k) by binary-searching how many elements each array contributes. Know that the O(log k) answer exists and roughly how it partitions, even if you would only implement it when pushed. The question is linked in the practice section.

Tie-breakers are comparator tests wearing a warm-up costume

Asked at Bytedance — Return the Most Frequent Integer with a Stable Tie-Breaker The warm-up in a two-problem round: given an integer array, return the most frequent element, and when two elements tie on frequency, return the smaller one. The submitted approach was a single pass maintaining the running best (count, value) pair while building the frequency map.

A tie-break clause looks like it was added to make the problem well-defined. It is actually the graded part of the warm-up: it checks whether you can order elements by a compound key (frequency descending, then value ascending) without garbling one of the directions.

For k = 1, skip the selection machinery entirely. Track (best_count, best_value) while counting, and update when count > best_count, or when count == best_count and value < best_value. One pass, O(n) time, O(u) space, no heap. Reaching for a heap here signals pattern-matching over thinking. The Squarepoint version of the same question — Find the Most Frequent Character with a Tie-Breaker, most frequent character, lexicographically smaller wins ties — was the problem the candidate reported overcomplicating, burning so much time that the interviewer never got to follow-up questions.

For general k with ties, the compound key has to survive your data structure's ordering conventions, and this is where sign errors breed:

• Sorting: sorted(counts.items(), key=lambda p: (-p[1], p[0]))[:k] — negate the count so bigger counts come first, leave the value positive so smaller values win ties. Clean, but you are back to O(u log u).
• Min-heap of size k: the heap top must be the worst element under the compound order. Worst means lowest count, and among equal counts, the largest value (since smaller values are preferred, larger ones should be evicted first). That means pushing (freq, -value), and now the negation lives in the eviction order and you must un-negate on extraction. Trace it on paper with a two-way tie before trusting it.

The honest recommendation: under interview pressure, if ties matter and k > 1, use the sort with an explicit key function and say you are trading the log factor for a comparator you can verify by reading. An interviewer who wants the heap will ask, and you will have banked the correct version first.

Practice these on PracHub

Grouped by the specific skill each one drills. Warm up left to right.

Counting and tie-breaking (get these airtight first):

• Find the Most Frequent Character with a Tie-Breaker (Squarepoint) — the k=1 compound-key pass; solvable in six lines, easy to overthink.
• Return the Most Frequent Integer with a Stable Tie-Breaker (Bytedance) — same skill on integers, asked as a timed warm-up before a harder tree problem.

The core pattern:

• Return the Most Frequent Values in an Array (Google) — the canonical top-k-frequent with the "beat O(n log n)" follow-up; bucket sort is the intended endpoint.
• Retain Top K Elements (Microsoft) — top-k with an output twist (filter the original list) that tests whether your selection step produces a usable membership set.
• Find the Most Frequent Log Call (Roblox) — the pattern in production clothes: most frequent call in a log, with extensions.

Heap under real constraints:

• Find the K Closest Points to the Origin (Asana) — non-integer ranking key, n >> k; the question that proves why bucket sort has boundaries.
• Find Kth Largest and Tree Ancestors (Meta) — quickselect territory, with the edge-case pressure of live test cases.

Merge-frontier variants:

• Return the K Smallest Values from Sorted Arrays (eBay) — the k-way merge, with an interviewer who rejects the dump-everything heap.
• Find the Kth Largest in Two Sorted Arrays (Glean) — the two-array special case with a binary-search escalation.

More frequency and heap questions, filterable by company, are in the coding questions bank.