Top K Frequent Elements

Return the k values that appear most often.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Top K Frequent Elements: Frequency is a bounded coordinate: place each value at its count, then scan counts from n down until k values are collected.

Input and goalReturn the `k` values that appear most often.

Count the concrete inputFor nums = [1,1,1,2,2,3] and k = 2, Counter produces 1 -> 3, 2 -> 2, and 3 -> 1.

101112232435

k2mapLabelfrequency

frequency132231

Recognize it

Use frequency buckets when the answer ranks values by occurrence count, counts cannot exceed the input length n, and linear time matters more than ordering values within equal-frequency buckets.

Keep true

Before scanning bucket f, the answer contains every value from frequencies greater than f and no value from a lower frequency. Therefore the first k collected values are among the k most frequent.

Reuse it

Whenever a ranking key is a small bounded integer, use that key as an array coordinate and scan coordinates in answer order; this transfers to counting sort, histogram selection, and bounded-score ranking.

Pattern: Frequency buckets.

Simple idea: Count each value. Put it in a bucket named by its count. Read buckets from high count to low count.

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
   frequencies = Counter(nums)
   buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]

   for num, frequency in frequencies.items():
      buckets[frequency].append(num)

   answer: list[int] = []
   for bucket in reversed(buckets):
      answer.extend(bucket)
      if len(answer) >= k:
         return answer[:k]
   return answer

Cost: $O(n)$ time and $O(n)$ space.