26. Top K Frequent Elements

Difficulty:MediumPattern:Bucket Sort / Frequency MapTime:O(n)Space:O(n)

Given an integer array nums and an integer k, return the k most frequent elements.

How It Works & Algorithmic Design

Solves using Bucket Sort Frequency Buckets:

Frequency Counting: Build a Hash Map freqMap counting occurrences of each number.
Bucket Array: Create an array of lists buckets of size nums.length + 1 where index $i$ represents frequency $i$.
Bucket Populating: For [num, freq] in freqMap, append num into buckets[freq].
Gather Top K: Loop backwards from bucket index nums.length down to 1 and collect elements until result.length === k.

Why This Approach Works Best

Bucket sort eliminates heap operations ($O(n \log k)$) to solve top-k frequency problems in linear $O(n)$ time and $O(n)$ space.

Example Walkthrough

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

Frequencies: 1->3, 2->2, 3->1.

Bucketing: bucket[3]=[1], bucket[2]=[2], bucket[1]=[3]

Elements bucketed by frequency.

Output: [1, 2]

Top 2 frequent items.

Answer: Top K Frequent Elements using Bucket Sort

function topKFrequent(nums, k) {
  const map = {};
  for (const num of nums) map[num] = (map[num] || 0) + 1;
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of Object.entries(map)) buckets[count].push(Number(num));
  const res = [];
  for (let i = buckets.length - 1; i >= 0 && res.length < k; i--) {
    if (buckets[i].length > 0) res.push(...buckets[i]);
  }
  return res.slice(0, k);
}

💡 Group numbers into frequency buckets and gather top K items from highest frequency downward.

Key Takeaways

Frequency cannot exceed array length $n$, making array buckets valid.
Bucket sort achieves true linear $O(n)$ time complexity.
Avoids $O(n \log n)$ sorting and $O(n \log k)$ heap overhead.