Top K Frequent Elements — Solution

Problem

Given an integer array and a count k, return the k elements that appear most frequently. The problem guarantees that the k-th and (k+1)-th most frequent elements always have different frequencies, so there is exactly one valid answer.

• Input: nums = [1, 1, 1, 2, 2, 3], k = 2
• Output: [1, 2]
• Explanation: 1 appears 3 times and 2 appears 2 times, making them the two most frequent elements.

Intuition

Every approach starts the same way — build a frequency map in O(n). The question is how to extract the top k entries efficiently. Sorting the map by frequency works but costs O(n log n). A min-heap of size k improves this to O(n log k) by evicting the least-frequent element whenever the heap grows too large. The best approach exploits the fact that frequencies are bounded by n: use frequency as an array index (bucket sort), then scan from the highest index down — no comparisons needed at all, just O(n).

Approach 1 — Sorting

Count each element's frequency, sort the unique elements by frequency in descending order, and return the first k.

Steps:

1. Build a frequency map over nums.
2. Extract the unique elements into a list.
3. Sort the list by frequency, highest first.
4. Return the first k elements.

1from collections import Counter
2
3def topKFrequent(nums: list[int], k: int) -> list[int]:
4    frequency = Counter(nums)
5    # sort unique elements by count descending; take the first k
6    return sorted(frequency.keys(), key=lambda num: -frequency[num])[:k]

• Time: O(n log n) — sorting the unique elements dominates; counting is O(n)
• Space: O(n) — the frequency map and sorted list each scale linearly with input size

Approach 2 — Min-Heap of Size k

Maintain a min-heap capped at size k, ordered by frequency with the least-frequent element on top. When the heap would exceed size k, evict the top — discarding the element with the lowest frequency. Whatever survives in the heap at the end is the answer.

Steps:

1. Build a frequency map over nums.
2. Initialize an empty min-heap.
3. For each unique element, push (frequency, element) onto the heap.
4. If the heap size exceeds k, pop the minimum — this evicts the least-frequent element.
5. Return the elements remaining in the heap.

1import heapq
2from collections import Counter
3
4def topKFrequent(nums: list[int], k: int) -> list[int]:
5    frequency = Counter(nums)
6    min_heap = []  # (freq, num); Python heapq is a min-heap by default
7
8    for num, freq in frequency.items():
9        heapq.heappush(min_heap, (freq, num))
10        if len(min_heap) > k:  # evict least frequent so heap stays at most size k
11            heapq.heappop(min_heap)
12
13    return [num for freq, num in min_heap]

• Time: O(n log k) — each of the n push/pop operations on the size-k heap costs O(log k)
• Space: O(n + k) — O(n) for the frequency map and O(k) for the heap

Approach 3 — Bucket Sort

An element's frequency is always between 1 and n. That bound lets us use frequency as an array index: create n + 1 buckets where buckets[i] holds every element that appears exactly i times. Scanning buckets from the highest index down gives elements in frequency order without any comparisons.

Steps:

1. Build a frequency map over nums.
2. Create n + 1 empty buckets (indices 0 through n).
3. For each unique element, append it to buckets[frequency].
4. Walk bucket indices from n down to 1, appending elements to the result.
5. Return once the result contains k elements.

1from collections import Counter
2
3def topKFrequent(nums: list[int], k: int) -> list[int]:
4    frequency = Counter(nums)
5    # buckets[i] holds all elements appearing exactly i times; max freq = len(nums)
6    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
7
8    for num, freq in frequency.items():
9        buckets[freq].append(num)
10
11    result = []
12    for freq in range(len(buckets) - 1, 0, -1):  # scan from highest frequency down
13        for num in buckets[freq]:
14            result.append(num)
15            if len(result) == k:  # early exit the moment k elements are collected
16                return result
17
18    return result

• Time: O(n) — counting is O(n), filling buckets is O(n), scanning buckets is O(n) worst case
• Space: O(n) — the frequency map and bucket array each scale linearly with input size

Complexity Summary

Common Mistakes

• Using a max-heap over all elements instead of a min-heap of size k: pushing everything into a max-heap and popping k times is O(n log n) — you've recreated sorting. The O(n log k) gain comes specifically from a min-heap capped at k that evicts as you insert.
• Bucket array size n instead of n + 1: when all elements are identical, frequency equals n, requiring bucket index n to be valid — the array must have size n + 1.
• Placing the early-exit check in the outer loop instead of the inner: if you check collected == k only after finishing an entire bucket, you can overshoot k when multiple elements share the same frequency.
• Expecting the min-heap result to be frequency-ordered: the min-heap approach guarantees only that the k survivors are the top-k by frequency — they are not sorted within that group. If the caller needs them ordered by frequency, sort after.
• Forgetting the unique-frequency guarantee: this problem ensures no tie between the k-th and (k+1)-th frequencies. Related problems like top-k-frequent-words drop that guarantee and require a lexicographic tiebreak, which changes the comparator.

Related Problems

• top-k-frequent-words — identical frequency counting pattern with an added lexicographic tiebreak for equal counts
• kth-largest-element-in-an-array — k-th selection using a heap or quickselect
• sort-characters-by-frequency — same frequency counting idea, but the output is the full string sorted by count rather than a top-k selection
• find-k-closest-elements — k-element selection with a proximity ordering instead of a frequency ordering
• last-stone-weight — max-heap manipulation on a dynamically changing collection