Top K Frequent Elements

PracticeNeetCode ↗LeetCode ↗

Given an integer array nums and an integer k, return the k most frequent elements. The answer can be in any order.

Example

Key Pointers

• Frequencies are bounded by n (a number can appear at most n times) — that bound is what makes bucket sort possible in O(n).
• A heap or full sort also works, but costs O(n log n); bucket sort skips the log factor entirely.
• Walking buckets from the highest frequency down naturally yields the top-k without any comparison sort.

Step-by-Step Analysis

1. Count each number's frequency with a hashmap.
2. Create buckets, an array of length n+1, where buckets[f] holds every number with frequency f.
3. Place each number into buckets[count[num]].
4. Walk buckets from index n down to 1, collecting numbers into the result until it has k elements.

Complexity

Time: O(n) — Space: O(n)

Code

def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = {}
    for n in nums:
        count[n] = count.get(n, 0) + 1

    buckets = [[] for _ in range(len(nums) + 1)]
    for n, freq in count.items():
        buckets[freq].append(n)

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

Code Explanation

How the solution above works, piece by piece.

1. First loop: count how often each number appears.
2. buckets = [[] for _ in range(len(nums) + 1)]: index = frequency. No number can appear more than len(nums) times, so this is always big enough.
3. buckets[freq].append(n): file each number under its count. This replaces sorting by frequency, which would cost O(n log n).
4. Walk freq from high to low and collect numbers until k are gathered, then return.
5. Every step is linear: O(n) time and O(n) space. That's the bucket-sort trick: frequencies are small integers, so they can be array indices.

Visual Walkthrough

Running it on nums = [1, 1, 1, 2, 2, 3], k = 2:

Video Explanation

NeetCode — Top K Frequent Elements, Bucket Sort, LeetCode 347