Top K Frequent Elements: Bucket Sort Trick

Top K Frequent Elements (LeetCode 347) is one of those problems where the "good enough" solution uses a heap, but the truly elegant solution uses bucket sort. Both pass, but bucket sort is O(n) while the heap approach is O(n log k). Interviewers love seeing both, and the bucket sort version is surprisingly simple once you see the trick.

Let's build it up from scratch.

The problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. It is guaranteed that the answer is unique.

Example: nums = [1, 1, 1, 2, 2, 3], k = 2

Output: [1, 2] because 1 appears 3 times and 2 appears 2 times. Those are the top 2 most frequent.

The first step is always the same: count the frequencies. After that, the question is how to efficiently find the k elements with the highest counts.

The heap approach (O(n log k))

The most natural approach after counting frequencies is to use a min-heap of size k. Walk through the frequency map, push each element onto the heap, and if the heap grows larger than k, pop the smallest. At the end, the heap contains exactly the k most frequent elements.

import heapq
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)
    return heapq.nlargest(k, counts.keys(), key=counts.get)

Python's heapq.nlargest does the heap management for you. Under the hood it maintains a min-heap of size k, which is exactly what you would write manually:

import heapq
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)
    heap = []
    for num, freq in counts.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for freq, num in heap]

This works. It is clean. But we can do better.

Time: O(n log k). Counting is O(n). Each heap operation is O(log k), and we do it for up to n distinct elements.

Space: O(n) for the frequency map, O(k) for the heap.

The follow-up question on LeetCode 347 literally asks: "can you do better than O(n log n)?" The heap approach already does O(n log k), which is better. But bucket sort gets us to O(n).

The bucket sort trick (O(n))

Here is the insight that makes bucket sort work for this problem: the maximum possible frequency of any element is n (the length of the array). So you can create an array of n + 1 buckets, where bucket i holds all elements that appear exactly i times.

The algorithm:

1. Count the frequency of each element (hash map)
2. Create buckets: an array of lists with indices from 0 to n
3. Place each element into the bucket matching its frequency
4. Walk the buckets from right (highest frequency) to left, collecting elements until you have k

That is it. No heap. No sorting. Just two linear passes.

The code

Here is the bucket sort solution in Python:

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]

    for num, freq in counts.items():
        buckets[freq].append(num)

    result = []
    for freq in range(len(buckets) - 1, 0, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Let's break it down:

• counts = Counter(nums) builds the frequency map. For [1,1,1,2,2,3] this gives {1: 3, 2: 2, 3: 1}. This is the frequency counter building block.
• buckets = [[] for _ in range(len(nums) + 1)] creates n + 1 empty lists. Index 0 will never be used (no element has frequency 0). Index n could hold an element that appears in every position.
• The first loop places each number into the bucket matching its frequency. Number 1 has frequency 3, so it goes in buckets[3]. Number 2 has frequency 2, so buckets[2]. Number 3 has frequency 1, so buckets[1].
• The second loop walks from the highest bucket down to 1. It collects elements until we have k of them. Since higher buckets contain more frequent elements, this naturally gives us the top k.

Complexity analysis

Bucket sort approach:

Time: O(n). Counting frequencies is O(n). Creating the buckets is O(n). Placing elements into buckets is O(n) because there are at most n distinct elements. Walking the buckets to collect k elements is at most O(n). Everything is linear.

Space: O(n). The frequency map holds at most n entries. The bucket array has n + 1 slots. The total extra space is proportional to n.

Compare this to the heap approach at O(n log k). For small k, the difference is minimal. But for large k (close to n), the bucket sort approach is measurably faster. And the code is arguably simpler.

Why bucket sort works here (and not everywhere)

Bucket sort is not a general-purpose replacement for comparison-based sorting. It works here because we have a tight bound on the range of values we are sorting by. The frequency of any element is between 1 and n, which means we need at most n + 1 buckets. The bucket array fits in memory, and we can fill it in one pass.

If the frequencies could be arbitrarily large (not bounded by n), bucket sort would not work. But in this problem, the constraint is baked into the input: you cannot have more occurrences of an element than there are elements in the array.

This is a good pattern to recognize: whenever you need to sort by a value that falls in a known, bounded range, bucket sort (or counting sort) can give you O(n) performance.

Edge cases to watch for

• k equals the number of distinct elements. You need to return everything. Bucket sort handles this fine since it walks all the buckets.
• All elements are the same. nums = [5, 5, 5], k = 1. One entry in the frequency map, one element in bucket n. Works.
• All elements are distinct. Every element has frequency 1. Bucket 1 has n elements. You pick any k of them. Since the problem guarantees a unique answer, this scenario with k is less than n and all frequencies equal would not appear in the test cases.

The building blocks

This problem is built from one core building block:

Frequency counter

Count how many times each element appears. This is the exact same building block used in Valid Anagram, Contains Duplicate, and Group Anagrams. The template:

from collections import Counter

counts = Counter(items)
# or manually:
counts = {}
for item in items:
    counts[item] = counts.get(item, 0) + 1

What makes Top K Frequent Elements interesting is the second step after counting. The frequency counter gives you a map from element to count. The bucket sort trick inverts that map: it gives you a mapping from count to elements. That inversion is the key insight, and it is what upgrades this from O(n log k) to O(n).

Problems that use the same bricks

The frequency counter building block shows up constantly:

• Group Anagrams: count character frequencies to generate canonical keys, then group by key
• Valid Anagram: count character frequencies in both strings and compare
• Sort Characters By Frequency: almost the same problem as Top K Frequent Elements, but you return all characters ordered by frequency. Bucket sort works perfectly here too.
• Top K Frequent Words: same idea but with a tiebreaker (lexicographic order). The heap approach handles tiebreakers more naturally than bucket sort.

Why you will forget this (and how to fix it)

The frequency counting part is easy to remember. You have probably written Counter(nums) a dozen times. The part that slips away is the bucket sort step. When you are under pressure, the heap approach feels safe and automatic. You reach for heapq.nlargest and move on.

But the bucket sort version is only five lines of code beyond the frequency count. The key insight to lock in is: "frequency is bounded by n, so I can use frequency as an array index." That single sentence is the difference between O(n log k) and O(n).

Spaced repetition is how you make it stick. Type the bucket sort solution from scratch, not just the Counter call. After a few reps at increasing intervals, the "create buckets, fill by frequency, walk backwards" sequence becomes automatic. You do not even think about it. You just reach for the right tool.

Related posts

• Hash Map Patterns - Top K Frequent Elements uses the frequency counting pattern, one of the three core hash map techniques
• Group Anagrams - Another hash map problem that uses frequency counting as a building block, with a different second step (grouping instead of sorting)

---

Visual Learner? Understand why bucket sort is O(n) with our Big O Notation Guide.