Top K Frequent Elements

The problem

Given an integer array and a number k, return the k values that appear most often, in any order.

The obvious route is to count frequencies and sort by them — O(n log n). A heap of size k trims that a little, but there's a sharper idea hiding in the structure of the problem.

The approach

First tally every value with a frequency map. The key observation: a value's frequency can never exceed the array's length, so frequencies live in a small, bounded range.

Build an array of buckets indexed by frequency — `buckets[f]` holds every value seen exactly `f` times. Then sweep from the highest frequency downward, collecting values until I have k of them. No sorting and no heap, just two linear passes and a walk over the buckets.

The solution

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

  // buckets[f] holds every value that appears exactly f times
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [value, count] of freq) buckets[count].push(value);

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

Time O(n)Space O(n)