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.

Practice

1. What is the main purpose of using a heap in the Top K Frequent Elements problem?

easy

A. To store elements without any order

B. To sort all elements in ascending order

C. To remove duplicates from the list

D. To efficiently keep track of the top K frequent elements by frequency

Solution

1. Step 1: Understand the problem goal

   The goal is to find the K elements that appear most frequently in a list.

2. Step 2: Role of heap in this context

   A heap helps efficiently keep track of the top K elements by frequency without sorting the entire list.

3. Final Answer:

   To efficiently keep track of the top K frequent elements by frequency -> Option D

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps top K elements efficiently by frequency [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple array storage
• Assuming heap removes duplicates

2. Which of the following TypeScript code snippets correctly initializes a min-heap to store pairs of [frequency, element] for the Top K Frequent Elements problem?

easy

A. const minHeap = new MinPriorityQueue<{freq: number, val: number}>({priority: x => x.freq});

B. const minHeap = new Array();

C. const minHeap = new Map();

D. const minHeap = new Set<[number, number]>();

Solution

1. Step 1: Identify correct heap initialization syntax

   TypeScript with modern libraries uses MinPriorityQueue with a priority function for min-heap.

2. Step 2: Check each option

   const minHeap = new MinPriorityQueue<{freq: number, val: number}>({priority: x => x.freq}); correctly creates a min-heap with priority based on frequency. Others are arrays, maps, or sets which do not provide heap behavior.

3. Final Answer:

   const minHeap = new MinPriorityQueue<{freq: number, val: number}>({priority: x => x.freq}); -> Option A

4. Quick Check:

   MinPriorityQueue with priority function = correct heap [OK]

Hint: Use MinPriorityQueue with priority function for min-heap [OK]

Common Mistakes:

• Using Array instead of heap
• Using Map or Set which are not heaps
• Missing priority function in heap initialization

3. What will be the output of the following TypeScript code snippet for nums = [1,1,1,2,2,3] and k = 2?

function topKFrequent(nums: number[], k: number): number[] {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }
  const minHeap = new MinPriorityQueue<{val: number, freq: number}>({priority: x => x.freq});
  for (const [num, freq] of freqMap.entries()) {
    minHeap.enqueue({val: num, freq});
    if (minHeap.size() > k) {
      minHeap.dequeue();
    }
  }
  const result = [];
  while (minHeap.size() > 0) {
    result.push(minHeap.dequeue().element.val);
  }
  return result.reverse();
}
console.log(topKFrequent([1,1,1,2,2,3], 2));

medium

A. [3, 2]

B. [1, 2]

C. [2, 1]

D. [1, 3]

Solution

1. Step 1: Calculate frequencies

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

2. Step 2: Use min-heap to keep top 2 frequent elements

   Insert (1,3), (2,2), (3,1). When size > 2, remove smallest freq. So 3 with freq 1 is removed.

3. Step 3: Extract elements from heap and reverse

   Heap contains (1,3) and (2,2). Extracted order reversed gives [1, 2].

4. Final Answer:

   [1, 2] -> Option B

5. Quick Check:

   Top 2 frequent = [1, 2] [OK]

Hint: Keep heap size ≤ k, remove smallest frequency [OK]

Common Mistakes:

• Not reversing result array
• Removing wrong element from heap
• Confusing frequency counts

4. Identify the bug in the following TypeScript code for finding top K frequent elements:

function topKFrequent(nums: number[], k: number): number[] {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, freqMap.get(num) + 1);
  }
  const minHeap = new MinPriorityQueue<{val: number, freq: number}>({priority: x => x.freq});
  for (const [num, freq] of freqMap.entries()) {
    minHeap.enqueue({val: num, freq});
    if (minHeap.size() > k) {
      minHeap.dequeue();
    }
  }
  const result = [];
  while (minHeap.size() > 0) {
    result.push(minHeap.dequeue().element.val);
  }
  return result.reverse();
}

medium

A. Map should be replaced with Set

B. minHeap.dequeue() removes wrong element

C. freqMap.get(num) + 1 causes error when num not in map

D. result.reverse() is unnecessary

Solution

1. Step 1: Check frequency map update line

   freqMap.get(num) returns undefined if num not present, so undefined + 1 causes NaN.

2. Step 2: Correct way to update frequency

   Use freqMap.get(num) || 0 to default to 0 if undefined, then add 1.

3. Final Answer:

   freqMap.get(num) + 1 causes error when num not in map -> Option C

4. Quick Check:

   Undefined + 1 = NaN error [OK]

Hint: Use (freqMap.get(num) || 0) + 1 to avoid undefined [OK]

Common Mistakes:

• Not handling undefined in map get
• Removing wrong element from heap
• Thinking reverse is unnecessary
• Replacing Map with Set incorrectly

5. Given a large array nums with many elements having the same frequency, how can you modify the heap approach to ensure the Top K Frequent Elements always returns the smallest elements when frequencies tie? Choose the best approach.

hard

A. Use a heap with priority comparing frequency first, then element value to break ties

B. Sort the entire array before building the heap

C. Use a max-heap instead of a min-heap without tie-break logic

D. Ignore tie cases as they do not affect the result

Solution

1. Step 1: Understand tie frequency problem

   When multiple elements share frequency, we want consistent ordering by element value.

2. Step 2: Modify heap priority to handle ties

   Use a comparator that first compares frequency, then element value to break ties, ensuring smallest elements come first.

3. Step 3: Why other options fail

   Sorting entire array is inefficient; max-heap without tie-break can give inconsistent results; ignoring ties causes unpredictable output.

4. Final Answer:

   Use a heap with priority comparing frequency first, then element value to break ties -> Option A

5. Quick Check:

   Priority with tie-break = correct tie handling [OK]

Hint: Add tie-break by element value in heap priority [OK]

Common Mistakes:

• Sorting entire array wastes time
• Ignoring tie-break leads to wrong output
• Using max-heap without tie-break causes inconsistency