Top K Frequent Elements

The problem

Given nums and k, return the k most frequent elements. Order of the answer can be any.

Input:  nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Brute force

Count frequencies, sort unique keys by count descending, take k. O(u log u).

function topKFrequentSort(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Optimal: bucket by frequency

Frequencies are in 1..n. Buckets[i] = list of nums with count i. Scan buckets from high to low.

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);

  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }

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

Heap alternative

Min-heap of size k on frequencies: O(n log k). Good when k ≪ n and you have a heap library.

Time	O(n) bucket / O(n log k) heap / O(n log n) full sort
Space	O(n)

Edge cases

• k = 1
• All unique → any k elements (freq 1)
• All same → that one element
• Ties — any valid set of k is OK unless problem requires sorted

Common bugs

• Sorting the whole array instead of unique keys
• Off-by-one bucket length
• Returning frequencies instead of values

Interview delivery

1. Count first.
2. Prefer bucket O(n) or heap O(n log k).
3. Code buckets cleanly.
4. State complexity.
5. Compare to sort.

Related

• Task Scheduler
• Group Anagrams
• Valid Anagram
• K Closest Points

Bucket layout for [1,1,1,2,2,3], k=2

Frequencies: 1→3, 2→2, 3→1.
buckets[3]=[1], buckets[2]=[2], buckets[1]=[3].
Scan from 3 downward → pick 1, then 2. Done.

Heap vs bucket choice

• Bucket: O(n) time, O(n) space — best when counts ≤ n (always for frequencies).
• Min-heap size k: O(n log k) — better language support sometimes; use when streaming.
• Full sort of uniques: simplest code if n is tiny.

Stability and ties

Problem allows any order and any valid k-set when frequencies tie. Don’t over-engineer secondary sorts unless asked.

Follow-ups

• Top K frequent words (lexicographic ties).
• Frequency stack / sort characters by frequency.
• Approximate top-k with count-min sketch (systems flex).

Further reading

• LeetCode 347 — Top K Frequent Elements
• Bucket sort