Top K Frequent Elements Using Heap in DSA Typescript

Mental Model

We want to find the k numbers that appear most often in a list by counting frequencies and using a small structure to keep track of the top counts.

Analogy: Imagine you have a bag of colored balls and want to find the k colors you have the most of. You count how many balls of each color you have, then keep only the top k colors in a small box that always removes the least frequent color when a new more frequent one comes in.

Input array: [1,1,1,2,2,3]
Frequency map: {1:3, 2:2, 3:1}
Min-heap (size k=2):
  [2:2]
  [1:3]
Heap keeps smallest frequency on top -> so if a new element has frequency > top, it replaces it.

Dry Run Walkthrough

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

Goal: Find the 2 numbers that appear most frequently in nums

Step 1: Count frequency of each number

{1:3, 2:2, 3:1}

Why: We need to know how often each number appears to find the top k frequent

Step 2: Add (1,3) to min-heap

Heap: [(1,3)]

Why: Start building heap with first frequency

Step 3: Add (2,2) to min-heap

Heap: [(1,3), (2,2)]

Why: Heap size less than k, so add next frequency

Step 4: Add (3,1) to min-heap, but frequency 1 < min frequency in heap (2), so ignore

Heap: [(2,2), (1,3)]

Why: Keep only top k frequencies, ignore smaller ones

Step 5: Extract elements from heap for result

Result: [1, 2]

Why: Heap contains top k frequent elements

Result:

Heap final: [(2,2), (1,3)]
Top 2 frequent elements: [1, 2]

Annotated Code

DSA Typescript

class MinHeap {
  heap: Array<[number, number]> = [];

  size() {
    return this.heap.length;
  }

  peek() {
    return this.heap[0];
  }

  swap(i: number, j: number) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parent = Math.floor((index - 1) / 2);
      if (this.heap[parent][1] <= this.heap[index][1]) break;
      this.swap(parent, index);
      index = parent;
    }
  }

  heapifyDown() {
    let index = 0;
    let length = this.heap.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.heap[left][1] < this.heap[smallest][1]) {
        smallest = left;
      }
      if (right < length && this.heap[right][1] < this.heap[smallest][1]) {
        smallest = right;
      }
      if (smallest === index) break;
      this.swap(index, smallest);
      index = smallest;
    }
  }

  push(val: [number, number]) {
    this.heap.push(val);
    this.heapifyUp();
  }

  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const top = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.heapifyDown();
    return top;
  }
}

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

  const minHeap = new MinHeap();

  for (const [num, freq] of freqMap.entries()) {
    if (minHeap.size() < k) {
      minHeap.push([num, freq]); // add until heap size k
    } else if (freq > minHeap.peek()![1]) {
      minHeap.pop(); // remove smallest freq
      minHeap.push([num, freq]); // add current
    }
  }

  const result: number[] = [];
  while (minHeap.size() > 0) {
    result.push(minHeap.pop()![0]);
  }
  return result.reverse();
}

// Driver code
const nums = [1,1,1,2,2,3];
const k = 2;
console.log(topKFrequent(nums, k).join(' -> ') + ' -> null');

for (const num of nums) { freqMap.set(num, (freqMap.get(num) ?? 0) + 1); }

Count frequency of each number

if (minHeap.size() < k) { minHeap.push([num, freq]); }

Add elements to heap until size k

else if (freq > minHeap.peek()![1]) { minHeap.pop(); minHeap.push([num, freq]); }

Replace smallest frequency if current is bigger

while (minHeap.size() > 0) { result.push(minHeap.pop()![0]); }

Extract elements from heap for final result

Output

1 -> 2 -> null

Complexity Analysis

Time: O(n log k) because we count frequencies in O(n) and maintain a heap of size k with O(log k) operations for each unique element

Space: O(n) for the frequency map and heap storing up to k elements

vs Alternative: Using sorting on all unique elements would be O(n log n), which is slower when k is much smaller than n

Edge Cases

Empty input array

Returns empty array since no elements exist

DSA Typescript

for (const num of nums) { freqMap.set(num, (freqMap.get(num) ?? 0) + 1); }

k equals number of unique elements

Returns all unique elements sorted by frequency

DSA Typescript

if (minHeap.size() < k) { minHeap.push([num, freq]); }

All elements have same frequency

Returns any k elements since frequencies tie

DSA Typescript

else if (freq > minHeap.peek()![1]) { ... }

When to Use This Pattern

When asked to find the top k frequent items efficiently, use a heap to keep track of the k largest frequencies without sorting all elements.

Common Mistakes

Mistake: Using a max-heap and extracting all elements then slicing top k, which is less efficient
Fix: Use a min-heap of size k to keep only top k frequent elements during iteration

Mistake: Not counting frequencies correctly or forgetting to handle missing keys
Fix: Use a map with default zero and increment counts properly

Summary

Finds the k most frequent elements in a list using a frequency map and a min-heap.

Use when you need the top k frequent items efficiently without sorting all elements.

Keep a min-heap of size k to track the top frequencies, replacing the smallest when a bigger frequency appears.