DSA Top K Frequent Elements

The problem

Top K Frequent Elements finds the k values that appear most often in a list. The answer lists those values from the highest count down.

Equal counts need one fixed tie rule. This article orders tied values from smallest to largest. That rule keeps the printed answer the same on every run.

cases = [
    ([1, 1, 1, 2, 2, 3], 2, [1, 2]),
    ([4, 4, 5, 5, 6, 6], 2, [4, 5]),
    ([7], 1, [7]),
    ([1, 2, 3], 3, [1, 2, 3]),
]
for nums, k, expected in cases:
    print("nums", nums, "k", k, "->", expected)

The second case is a three-way tie at two appearances each. The tie rule takes 4 and then 5. The last case takes every value, because k equals the number of distinct values.

Intuition: grab the biggest count, again and again

A first idea counts the values once. Then it scans the counts for the largest one and takes that value. It repeats the scan until k values are taken.

The idea works. Its cost hides in the repeats. Each new answer value pays a fresh scan over every distinct value still waiting.

freq = {1: 3, 2: 2, 3: 1}
taken = []
scans = 0
for _ in range(2):
    best = None
    for value in sorted(freq):
        scans += 1
        if value not in taken and (best is None or freq[value] > freq[best]):
            best = value
    taken.append(best)
print("top 2:", taken)
print("count entries scanned:", scans)

Two answers cost two full scans here. Ten answers over many distinct values cost ten scans. The counting work was done once, and then the ranking pays again and again.

Brute force: repeated maximum scans, counted

The brute force writes the intuition as a function. It counts first. Then each round scans every remaining entry for the largest count, with ties going to the smallest value.

def top_k_brute(nums, k):
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    taken = []
    scans = 0
    for _ in range(min(k, len(freq))):
        best = None
        for value in sorted(freq):
            if value in taken:
                continue
            scans += 1
            if best is None or freq[value] > freq[best]:
                best = value
        taken.append(best)
    return taken, scans

result, scans = top_k_brute([1, 1, 1, 2, 2, 3], 2)
print("top 2:", result)
print("entries scanned:", scans)
result, scans = top_k_brute([4, 4, 5, 5, 6, 6], 2)
print("tie case:", result)
print("entries scanned:", scans)

Each round scans the entries that are still in play. The scan count grows with both k and the distinct count. A full sort of the counts would also work, and it pays a sorting cost the buckets below avoid.

The optimal solution: place each value in the bucket named by its count

A frequency bucket is a list that holds every value with one given count. The bucket index is the count itself. Reading the buckets from the highest count down gives the ranking in one walk.

No count can pass the number of items in the list. A bucket list with one slot per item plus one is always long enough.

def top_k(nums, k):
    if k <= 0 or not nums:
        return []
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]
    for value, count in freq.items():
        buckets[count].append(value)
    result = []
    for count in range(len(buckets) - 1, 0, -1):
        for value in sorted(buckets[count]):
            result.append(value)
            if len(result) == k:
                return result
    return result

cases = [
    ([1, 1, 1, 2, 2, 3], 2, [1, 2]),
    ([4, 4, 5, 5, 6, 6], 2, [4, 5]),
    ([7], 1, [7]),
    ([1, 2, 3], 3, [1, 2, 3]),
]
for nums, k, expected in cases:
    result = top_k(nums, k)
    print("nums", nums, "k", k, "->", result, "match:", result == expected)

All four cases pass. Sorting happens only inside one bucket at a time, and only to fix the order of ties.

Walkthrough: [1, 1, 1, 2, 2, 3] with k at 2

The walk counts first. The state then becomes the bucket list. The answer is read straight off the buckets from the top.

nums = [1, 1, 1, 2, 2, 3]
freq = {}
for num in nums:
    freq[num] = freq.get(num, 0) + 1
print("counts:", {v: freq[v] for v in sorted(freq)})
buckets = [[] for _ in range(len(nums) + 1)]
for value in sorted(freq):
    buckets[freq[value]].append(value)
for count, bucket in enumerate(buckets):
    if bucket:
        print("bucket", count, "holds", bucket)
top = []
for count in range(len(buckets) - 1, 0, -1):
    top.extend(sorted(buckets[count]))
print("read from the top:", top[:2])

Bucket 3 holds the value 1. Bucket 2 holds the value 2. The first two values read from the top are the answer, and no further bucket is opened.

Complexity

The brute force scans the distinct entries once per answer value, so its ranking time grows with k times the distinct count. The bucket walk places each distinct value once and reads each bucket once, so its time is O(n) for n items.

The bucket list holds one slot per item plus one, and the buckets together hold each distinct value once, so the extra space is O(n). The frequency map also holds one entry per distinct value.

for distinct in [3, 6, 12]:
    k = distinct
    print("distinct", distinct, "- brute scans up to:", k * distinct, " bucket placements:", distinct)

When k grows with the distinct count, the brute scans grow quadratically. Placements grow in a straight line. Counting first turns a ranking problem into a bucket walk.

Edge cases and pitfalls

A k of zero asks for no values. A k beyond the distinct count returns every distinct value in ranked order. An empty list returns an empty answer.

def top_k(nums, k):
    if k <= 0 or not nums:
        return []
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]
    for value, count in freq.items():
        buckets[count].append(value)
    result = []
    for count in range(len(buckets) - 1, 0, -1):
        for value in sorted(buckets[count]):
            result.append(value)
            if len(result) == k:
                return result
    return result

print("k is zero:", top_k([1, 1, 2], 0))
print("empty list:", top_k([], 3))
print("k past distinct:", top_k([2, 2, 1], 5))
print("all the same:", top_k([9, 9, 9], 1))
print("negative values:", top_k([-1, -1, 0], 2))

The classic pitfall is an unstable tie. Two runs could order equal counts differently if the tie order came from dict order alone. Sorting inside each bucket removes that risk.