Q67: Top K Frequent Elements. - DSA Patterns (Multi-Lang)

In Simple Words: Bucket Sort in $O(N)$ time:

Count frequencies with Hash Map.
Group elements into an array of buckets where index is the frequency: buckets[freq] = [elements].
Iterate buckets backwards from $N$ down to 1 until $K$ elements are collected.

Time: $O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

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, c in count.items():
        buckets[c].append(n)
    res = []
    for i in range(len(buckets) - 1, 0, -1):
        for n in buckets[i]:
            res.append(n)
            if len(res) == k:
                return res
    return res