Top K Frequent Elements

This problem joins two patterns. A hash map counts; a heap picks the top. It shows up in screens at almost every large company, and the strong answer ends with a linear-time bucket solution that most candidates don't know.

The problem

Given an array of integers and a number k, return the k values that appear most often. You may return them in any order. The answer is guaranteed to be unique: there is never a tie at the edge of the top k.

• numbers = [5, 3, 5, 1, 3, 5, 7, 3, 5], k = 2 → [5, 3]. 5 appears 4 times, 3 appears 3 times, 1 and 7 once each.
• numbers = [9], k = 1 → [9].

Constraints: 1 ≤ n ≤ 10⁵, k is between 1 and the number of distinct values.

Clarifying questions

• Does the output need an order? No, any order.
• What if two values tie for the last place? The problem guarantees it cannot happen. If it could, ask which one to prefer and encode the rule in the key.
• Can values be negative? Yes. That rules out using the values as array indices, but not using the counts as indices, which the bucket solution does.

Approach 1: count, then sort

Count every value with a hash map. Sort the distinct values by count, largest first, and take the first k.

1from collections import Counter23def top_k_frequent_sort(numbers: list[int], k: int) -> list[int]:4    """Count, sort every distinct value by count, take the first k."""5    counts = Counter(numbers)6    ordered = sorted(counts, key=lambda value: counts[value], reverse=True)7    return ordered[:k]

Let m be the number of distinct values. Counting is O(n); sorting is O(m log m). Total O(n + m log m) time, O(m) space. When most values are distinct, m is close to n and this is O(n log n). It passes at n = 10⁵, but it sorts every value when you asked for k of them. The question is designed to push you below that.

The key insight

Once the counts are known, this is Kth Largest again, but over counts. You want the k values with the largest counts, so keep a min-heap of size k keyed by count. The least frequent value you are holding sits on top, ready to be evicted.

The heap stores (count, value) tuples. Count comes first, because heapq compares tuples field by field, and the first field is what you want to order by. The value rides along as the payload. Because values are integers, a tie on count falls through to comparing values, which is harmless.

There is an even better observation. A count can never be larger than n. So instead of comparing counts, you can use each count as an array index: put every value into bucket number count, then read buckets from n down to 1. No comparisons, no log.

Approach 2: count, then a size-k heap

1import heapq2from collections import Counter34def top_k_frequent_heap(numbers: list[int], k: int) -> list[int]:5    """Count, then keep the k most frequent values in a min-heap keyed by count."""6    counts = Counter(numbers)7    heap: list[tuple[int, int]] = []         # (count, value), smallest count on top8    for value, count in counts.items():9        heapq.heappush(heap, (count, value))10        if len(heap) > k:11            heapq.heappop(heap)              # drop the least frequent we hold12    return [value for _, value in heap]

Dry run on [5, 3, 5, 1, 3, 5, 7, 3, 5] with k = 2. The counts are {5: 4, 3: 3, 1: 1, 7: 1}, visited in that order.

The function returns [3, 5], which is the right set in a different order. Any order is accepted.

Complexity. Counting is O(n). Each of the m distinct values does one push and at most one pop on a heap of size k + 1: O(m log k). Total O(n + m log k) time, O(m + k) space for the counter and the heap. When k is small, this is close to linear.

Python has a shortcut: Counter(numbers).most_common(k) does exactly this, using heapq.nlargest inside. Mention it — it shows you know the library — but expect the interviewer to ask you to write the heap yourself, since that is what the question tests.

Approach 3: bucket by count

1from collections import Counter23def top_k_frequent_buckets(numbers: list[int], k: int) -> list[int]:4    """Bucket values by count; walk the buckets from the highest count down."""5    counts = Counter(numbers)6    buckets: list[list[int]] = [[] for _ in range(len(numbers) + 1)]7    for value, count in counts.items():8        buckets[count].append(value)         # a count is never above len(numbers)9    result: list[int] = []10    for count in range(len(buckets) - 1, 0, -1):11        for value in buckets[count]:12            result.append(value)13            if len(result) == k:14                return result15    return result

On the example, buckets[4] = [5], buckets[3] = [3], buckets[1] = [1, 7]. Walking down from 9, the first two values met are 5, then 3. Result [5, 3].

Time O(n): counting is O(n), filling buckets is O(m), and the walk touches n + 1 buckets at most. Space O(n) for the buckets. This beats the heap on time, but the heap wins when the data is a stream or when you cannot allocate n + 1 buckets.

Edge cases

• All values the same, such as [2, 2, 2], k = 1: one distinct value, count 3. Both solutions return [2].
• All values distinct with k = m: every count is 1, and the problem's uniqueness guarantee means k must equal m; every value is returned.
• Negative values: fine, because only counts are used as indices.
• One element: [9], k = 1 returns [9].

Follow-ups

• "Return the top k words, most frequent first, ties broken alphabetically." Order matters now, and ties must be decided by the key. Sorting with the key (-count, word) does it in one line. A size-k heap needs a small wrapper class whose __lt__ puts lower counts, and alphabetically later words, on top, because you cannot negate a string.
• "The input is a stream and the answer is needed at any time." Keep the counter updated, and rebuild the top k from it on demand. For huge streams, an approximate counter such as Count-Min Sketch is the system-design answer.
• "Return them sorted by frequency." Pop the heap into a list and reverse it: the heap gives least frequent first.