Top K Frequent Elements

MediumArrays & HashingArrayHash TableHeap

Problem

You are given an integer array and a number k. Return the k values that occur most often; order does not matter, and a well-defined answer of size k is guaranteed to exist.

Example. For [1, 1, 1, 2, 2, 3] with k = 2, the answer is [1, 2], since 1 occurs three times and 2 occurs twice, more than 3.

Key idea

The first step is always the same: tally how often each distinct value occurs with a hash map, in one linear pass. From there, sorting the distinct values by frequency and taking the top k works, but sorting all of them is more effort than the problem needs when k is small.

A better approach keeps a min-heap of size k while scanning the distinct values: push each frequency in, and whenever the heap grows past k, pop the smallest. What remains after every distinct value is processed is exactly the k largest frequencies, at a cost of O(log k) per push or pop instead of O(log n). An even faster approach exploits the fact that frequency can never exceed the array length: build an array of buckets indexed by frequency, drop each value into the bucket matching its count, then walk the buckets from the highest frequency down, collecting values until k are gathered, with no sorting required.

Solution

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

  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []); // index = frequency, which can't exceed the array length
  for (const [value, count] of frequency) {
    buckets[count].push(value);
  }

  const result: number[] = [];
  for (let count = buckets.length - 1; count >= 0 && result.length < k; count--) { // walk buckets from highest frequency down
    for (const value of buckets[count]) {
      result.push(value);
      if (result.length === k) {
        break;
      }
    }
  }

  return result;
}

Complexity

  • Time: O(n) using bucket sort by frequency, since frequency is bounded by the array length; O(n log k) using a size-k heap instead.
  • Space: O(n). The frequency map and the bucket array both scale with the number of elements.

Watch out for

  • Use a min-heap of size k, not a max-heap over every element; discarding the smallest as the heap overflows is what keeps the work bounded by k rather than by the number of distinct values.
  • Bucket sort by frequency only works because the count is bounded by the array length, even though the values themselves can be arbitrary integers.

Pattern

This is "count, then select": tally frequencies first, then use a bounded-size heap or a bucket sort keyed by count to pick the top or bottom few without fully sorting everything.

Related questions