Top K Frequent Elements — Heap vs Bucket Sort

The problem

Given an array of integers and an integer k, return the k most frequent elements. You may return the answer in any order.

Example: nums = [1,1,1,2,2,3], k = 2 → [1,2]

“1” appears 3 times, “2” appears 2 times, “3” appears 1 time. The top 2 are [1, 2].

Step 1 is always the same — count the frequencies with a hash map (the pattern from Day 5):

// Step 1: frequency map — O(n)
const count = new Map();
for (const n of nums) {
  count.set(n, (count.get(n) || 0) + 1);
}
// count = Map { 1 => 3, 2 => 2, 3 => 1 }

Step 2 is where the approaches diverge: how do you extract the top k from the frequency map? Three answers: sort everything, maintain a small heap, or bucket by frequency.

Approach 1: Sort — O(n log n) time, O(n) space

Convert the map to an array of [num, count] pairs. Sort by count descending. Take the first k.

// Sort approach — O(n log n) time
function topKFrequentSort(nums, k) {
  const count = new Map();
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);

  const entries = [...count.entries()];  // [[1,3], [2,2], [3,1]]
  entries.sort((a, b) => b[1] - a[1]);   // sort by count DESC
  return entries.slice(0, k).map(e => e[0]); // [1, 2]
}

Simple and readable. But you’re sorting all unique elements when you only need the top k. If there are 10,000 unique elements and k=5, you sort all 10,000 just to throw away 9,995 of them. The sort is O(m log m) where m is the number of unique elements (m ≤ n).

Approach 2: Min-heap of size k — O(n log k) time

Instead of sorting everything, maintain a min-heap (priority queue) of size k. The heap stores the top k elements seen so far, with the smallest count at the root.

For each unique element: push it onto the heap. If the heap exceeds size k, pop the root (the element with the smallest count). When you’re done, the heap contains exactly the top k.

// Min-heap approach — O(n log k) time
function topKFrequentHeap(nums, k) {
  const count = new Map();
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);

  const heap = new MinHeap();  // min-heap by count
  for (const [num, cnt] of count) {
    heap.push({ num, count: cnt });
    if (heap.size() > k) heap.pop();  // evict smallest
  }
  // Heap now contains exactly k elements — the top k
  return heap.toArray().map(e => e.num);
}

Each heap operation (push + pop) costs O(log k) because the heap has at most k elements. With m unique elements, that’s O(m log k). Since m ≤ n, total time is O(n + m log k). When k is small (which it usually is — you want top 5, not top 50,000), log k is tiny and this is nearly O(n).

What is a min-heap? A binary heap is a complete binary tree where each parent is smaller than its children. The root is always the minimum element. Push and pop are O(log k) because the tree height is log₂(k). It’s implemented as an array: for element at index i, its children are at 2i+1 and 2i+2, its parent is at floor((i-1)/2).

Approach 3: Bucket sort — O(n) time

The frequency of any element is between 1 and n (it can appear at most n times). So create an array of n+1 “buckets” where bucket[i] holds all elements that appear exactly i times. Then scan the buckets from highest frequency down, collecting k elements.

// Bucket sort approach — O(n) time
function topKFrequentBucket(nums, k) {
  const count = new Map();
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);

  const n = nums.length;
  const buckets = new Array(n + 1).fill(null).map(() => []);
  //                ↑ index = frequency (1 to n)

  for (const [num, cnt] of count) {
    buckets[cnt].push(num);  // num appears cnt times
  }

  const result = [];
  for (let i = n; i >= 0 && result.length < k; i--) {
    for (const num of buckets[i]) {
      result.push(num);
      if (result.length === k) return result;
    }
  }
  return result;
}

No comparison sort. No heap. Just an array indexed by frequency. Building the buckets is O(m) = O(n). Scanning them is O(n). Total: O(n) — genuinely linear.

The benchmark — which is actually fastest?

I benchmarked all three approaches across five input sizes (30 runs each, median reported):

Input	Sort O(n log n)	Heap O(n log k)	Bucket O(n)	Fastest
n=1K, k=5	0.05ms	0.12ms	0.12ms	Sort
n=10K, k=10	0.22ms	0.36ms	0.56ms	Sort
n=50K, k=10	1.29ms	1.27ms	1.94ms	Heap
n=100K, k=10	2.55ms	2.68ms	4.44ms	Sort
n=1M, k=20	27.04ms	27.45ms	77.80ms	Sort

The surprise: bucket sort (O(n)) is the SLOWEST at every size tested. Sort and heap are nearly tied. This contradicts the Big O prediction. Why?

Why O(n) lost — constant factors:

• Bucket sort’s overhead: allocating an array of size n+1 (1,000,001 elements), initializing each as an empty array, then filling them — that’s huge constant-factor work. JavaScript arrays are objects with property lookups, not raw memory.
• Sort is fast because: V8’s sort() is implemented in C++ (TimSort). The frequency map has only m unique entries (not n), so the sort step is tiny. Most of the time is spent in the frequency-counting step (O(n)), which all three approaches share.
• The lesson: Big O describes asymptotic growth — what happens as n → ∞. It doesn’t predict who wins on real data with real hardware. When n is bounded (and it always is), constant factors dominate. Day 12 found the same thing: sort beat count at small n. Know the Big O for the interview. Benchmark for production.

When the heap actually wins

If bucket sort is slow and sort is fast, when does the heap actually win? Two scenarios:

1. Streaming data. If elements arrive one at a time and you need to maintain the top k continuously, the heap is the only option. You can’t re-sort or re-bucket on every element. Push each element, pop if size > k. The heap maintains the top k in O(log k) per element.
2. k is tiny relative to m. If you have 1 million unique elements and want the top 5, sorting all 1 million is wasteful. The heap does O(m log 5) = O(m × 2.3) work; the sort does O(m log m) = O(m × 20). The heap wins asymptotically — but only when m is large enough for the log factor to matter.

For LeetCode-style problems where you count frequencies once and extract k, the sort approach is usually the fastest in practice. But interviewers expect the heap or bucket sort answer because it demonstrates knowledge of data structures. Know all three. Explain the tradeoffs. Pick based on context.

The hash pattern — the complete family

The hash map pattern family is now complete. Each lesson used the same tool — a hash map — but asked a different question:

• Day 4 (Contains Duplicate): “Have I seen this before?” → hash set, O(1) membership check.
• Day 5 (Valid Anagram): “How many times does each character appear?” → hash map as frequency counter, O(1) counting.
• Day 11 (Two Sum): “What number do I need to reach the target?” → hash map for complement lookup, O(1) “what do I need?”
• Day 12 (Group Anagrams): “Which strings share the same letter signature?” → hash map with canonical key, O(n) grouping.
• Day 18 (Top K Frequent): “Which elements appear most often?” → hash map + heap/bucket, ranking by frequency.

The meta-pattern: hash maps answer questions in O(1). The question determines the key and value. The algorithm determines how you process the results.

Check your understanding