Top K Frequent Elements

Signal

"Top-K by frequency" (or any score bounded by n) is a strong signal for bucket sort, not a full sort — the answer wants O(n), and sorting everything costs O(n log n).

Approach

Count frequencies with a hash map. No value can appear more than n times, so build n+1 buckets indexed by frequency and place each distinct value into the bucket matching its count. Walk the buckets from highest frequency down, collecting values until you have k. This is bucket sort by frequency, and it's linear because the bucket range is bounded by input size, not value range.

Skeleton

freq = count(nums)                  # value -> count
buckets = [[] for _ in range(n+1)]  # index by count
for value, c in freq.items():
    buckets[c].append(value)
result = []
for c in range(n, 0, -1):
    for value in buckets[c]:
        result.append(value)
        if len(result) == k: return result

Solution

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    freq = Counter(nums)
    buckets: list[list[int]] = [[] for _ in range(n + 1)]
    for value, c in freq.items():
        buckets[c].append(value)

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

Complexity

O(n) time — counting is O(n), and the bucket pass visits at most n+1 buckets holding n values total. O(n) space for the counts and buckets.

Pitfalls

• A min-heap of size k (heapq.nlargest, or a manual heap) is the other standard answer at O(n log k) — correct, but don't call it O(n); only bucket sort hits true linear time here.
• Sorting all (value, count) pairs and slicing the top k is the tempting first instinct — O(n log n), strictly worse than either approach above.
• The problem only asks for a valid set of k values when frequencies tie at the boundary, not a specific tie-break — don't over-engineer that.