Top K Frequent Elements

Given an integer array and k, return the k most frequent elements. (LC 347)

This is the "top k" rep — and the rare problem where the expected answer isn't the obvious heap, because a counting insight beats it.

The recipe

Say before you type: "Count with a map. Then, instead of sorting the counts, notice a frequency can't exceed n — so an array indexed by frequency is a free bucket sort."

1. One pass: Map<value, count>.
2. Build buckets where buckets[f] holds every value occurring exactly f times. A value can appear at most n times, so n + 1 buckets always suffice.
3. Walk the buckets from the high end, collecting until you have k.

The code

function topKFrequent(nums: number[], k: number): number[] {
  const counts = new Map<number, number>();
  for (const n of nums) counts.set(n, (counts.get(n) ?? 0) + 1);

  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, c] of counts) buckets[c].push(num); // index = frequency

  const res: number[] = [];
  for (let f = buckets.length - 1; f >= 0 && res.length < k; f--) {
    for (const num of buckets[f]) {
      res.push(num);
      if (res.length === k) return res;
    }
  }
  return res;
}

Why this shape

Sorting the count entries costs O(n log n) and answers a more general question than asked — you don't need a total order, just the top of it. The bucket insight is that frequencies live in a bounded, dense range [1, n], and bounded ranges can be "sorted" by direct indexing. That's counting sort's trick, borrowed for one pass.

Give the ladder out loud: sort O(n log n) → heap of size k O(n log k) → buckets O(n). Naming all three and why you're picking the last is the answer.

Complexity

	Cost	Because
Time	O(n)	Three linear passes: count, bucket, collect
Space	O(n)	The count map and the bucket array

Traps

• Sizing the bucket array n instead of n + 1 — an element occurring n times (all-same array) indexes off the end.
• Walking the buckets low-to-high. The most frequent live at the top.
• With the heap variant: it's a min-heap of size k (evict the smallest), not a max-heap of everything — the whole point of log k.

The pattern this trains

"Top k / k most / k closest" → heap by reflex, buckets when the ranked quantity is a bounded integer (frequencies, ages, scores). K Closest Points (LC 973) is the same trigger where the heap is the answer — distances aren't bucketable.