The tell: 'k most frequent' — counting plus a partial ordering, not a full sort.
How you get there
1Count with a Counter in O(n).
2Frequencies are bounded by n, so bucket the values by frequency into an array of lists.
3Walk the buckets from the high end and take k — linear overall, beating a heap's O(n log k).
Solution
Python
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for value, freq in counts.items():
buckets[freq].append(value)
out: list[int] = []
for freq in range(len(buckets) - 1, 0, -1):
for value in buckets[freq]:
out.append(value)
if len(out) == k:
return out
return out
Time
O(n)
Space
O(n)
What goes wrong
Sizing the bucket array to max(counts) instead of len(nums) breaks when every element is distinct.