Top K Frequent Elements

Top K Frequent Elements looks like a sorting problem, but the best solution never sorts. It shows off a beautiful trick: bucket sort by count, which turns an O(n log n) job into a clean O(n) pass.

The slow way first

The obvious idea: count how often each value appears, then sort the values by their frequency and take the top k. Counting is O(n), but the sort is O(n log n).

The question to ask: do we actually need a full ordering? We only need the top k. Frequencies are small integers between 1 and n — and whenever you are "sorting" small bounded integers, you can often skip comparisons entirely and use them as array indices.

The idea: bucket by frequency

Build a list of buckets where the index is the frequency. buckets[f] holds every value that appears exactly f times. Then read the buckets from the highest index down and collect values until you have k of them.

The key insight: a frequency can be at most n, so a fixed array of n + 1 buckets covers every case. Placing values is O(n) and sweeping is O(n), so the whole thing is O(n) — no sort.

Walk through it

Step through the animation. First we scan nums once and fill the count map: {1: 3, 2: 2, 3: 1}. Then each value drops into the bucket matching its count — 3 into bucket 1, 2 into bucket 2, 1 into bucket 3. Finally we read buckets from the highest index down: bucket 3 gives us 1, bucket 2 gives us 2, and now we have k = 2 values, so we stop and return [1, 2].

Pseudocode

count = frequency of each value in nums      # O(n)
buckets = an empty list for each frequency 0..n
for each (value, freq) in count:
    put value into buckets[freq]
result = []
for freq from highest down to 1:
    for value in buckets[freq]:
        add value to result
        if result has k items: return result

The Python solution

def top_k_frequent(nums, k):
    count = Counter(nums)
    # buckets[f] = values that appear exactly f times
    buckets = [[] for _ in range(len(nums) + 1)]
    for val, freq in count.items():
        buckets[freq].append(val)
    result = []
    for freq in range(len(buckets) - 1, 0, -1):
        for val in buckets[freq]:
            result.append(val)
            if len(result) == k:
                return result

• Counter(nums) tallies every value in one O(n) pass.
• buckets has len(nums) + 1 slots so any frequency from 0 to n has a home; the index is the frequency.
• buckets[freq].append(val) files each value under its count — no comparisons, just indexing.
• The outer loop walks frequencies from high to low, so the first values we collect are the most frequent.
• We return the instant result reaches k, so we never scan more than we must.

Complexity

The heap approach (heapq.nlargest(k, count, key=count.get)) is a great, slightly shorter answer at O(n log k) — worth mentioning in an interview. Bucket sort wins on raw time because counts are bounded integers, so they become indices instead of things to compare.

When this pattern shows up

Practice