Top K Frequent Elements Using Heap in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top K Frequent Elements Using Min-Heap

What is the output of the following TypeScript code that finds the top 2 frequent elements using a min-heap?

DSA Typescript

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 heap: [number, number][] = [];

  for (const [num, freq] of freqMap.entries()) {
    if (heap.length < k) {
      heap.push([num, freq]);
      heap.sort((a, b) => a[1] - b[1]);
    } else if (freq > heap[0][1]) {
      heap[0] = [num, freq];
      heap.sort((a, b) => a[1] - b[1]);
    }
  }

  return heap.map(pair => pair[0]);
}

console.log(topKFrequent([1,1,1,2,2,3], 2));

A [3, 2]

B [2, 3]

C [1, 3]

D [1, 2]

💡 Hint

Count frequencies first, then keep only top k elements in a min-heap sorted by frequency.

The frequencies are: 1 -> 3 times, 2 -> 2 times, 3 -> 1 time. The top 2 frequent elements are 1 and 2. The heap keeps the smallest frequency at the root, so after processing all, it contains [1,3] and [2,2]. The output extracts the numbers only.

❓ Predict Output

intermediate

Output of Top K Frequent Elements with Different Input

What is the output of this TypeScript function call for top 3 frequent elements?

DSA Typescript

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 heap: [number, number][] = [];

  for (const [num, freq] of freqMap.entries()) {
    if (heap.length < k) {
      heap.push([num, freq]);
      heap.sort((a, b) => a[1] - b[1]);
    } else if (freq > heap[0][1]) {
      heap[0] = [num, freq];
      heap.sort((a, b) => a[1] - b[1]);
    }
  }

  return heap.map(pair => pair[0]);
}

console.log(topKFrequent([4,4,4,6,6,7,7,7,7,8], 3));

A [6, 7, 4]

B [7, 4, 6]

C [7, 8, 6]

D [4, 7, 8]

💡 Hint

Check frequencies: 4 appears 3 times, 6 appears 2 times, 7 appears 4 times, 8 appears once.

Frequencies: 7 -> 4, 4 -> 3, 6 -> 2, 8 -> 1. Top 3 are 7, 4, and 6. The heap keeps the smallest frequency at root, so after processing all, it contains these three numbers.

🔧 Debug

advanced

Identify the Error in Heap Implementation for Top K Frequent Elements

What error will occur when running this TypeScript code to find top 2 frequent elements?

DSA Typescript

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

  const heap: [number, number][] = [];

  for (const [num, freq] of freqMap.entries()) {
    if (heap.length < k) {
      heap.push([num, freq]);
      heap.sort((a, b) => a[1] - b[1]);
    } else if (freq > heap[0][1]) {
      heap[0] = [num, freq];
      heap.sort((a, b) => a[1] - b[1]);
    }
  }

  return heap.map(pair => pair[0]);
}

console.log(topKFrequent([1,1,2,2,2,3], 2));

A TypeError: Cannot read property '1' of undefined

B TypeError: Cannot read property 'get' of undefined

C TypeError: Cannot read property '1' of null

D TypeError: Cannot read property 'get' of null

💡 Hint

Check how freqMap.get(num) is used before adding 1.

The code does freqMap.get(num) + 1 without checking if freqMap.get(num) is undefined initially. This causes undefined + 1 which is NaN, but then freqMap.set(num, NaN) is stored. Later, sorting or comparisons cause TypeError when accessing undefined elements.

❓ Predict Output

advanced

Output of Top K Frequent Elements Using Max-Heap Simulation

What is the output of this TypeScript code that simulates a max-heap by sorting descending?

DSA Typescript

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 sorted = Array.from(freqMap.entries()).sort((a, b) => b[1] - a[1]);

  return sorted.slice(0, k).map(pair => pair[0]);
}

console.log(topKFrequent([5,5,5,6,6,7,7,7,7,8,8,8], 4));

A [7, 5, 8, 6]

B [5, 7, 8, 6]

C [7, 8, 5, 6]

D [8, 7, 5, 6]

💡 Hint

Count frequencies and sort descending by frequency.

Frequencies: 7 -> 4, 5 -> 3, 8 -> 3, 6 -> 2. Sorted descending: 7(4), 5(3), 8(3), 6(2). Top 4 are [7,5,8,6].

🧠 Conceptual

expert

Why Use a Min-Heap Instead of Max-Heap for Top K Frequent Elements?

Which reason best explains why a min-heap of size k is preferred over a max-heap of all elements when finding top k frequent elements?

A A min-heap sorts all elements in ascending order, which is faster than max-heap sorting.

B A max-heap cannot be implemented efficiently in TypeScript, so min-heap is the only option.

C A min-heap of size k keeps only the k largest frequencies efficiently, reducing memory and time complexity.

D A min-heap automatically removes duplicates, which max-heap does not.

💡 Hint

Think about how to keep track of only the top k elements without sorting all.

Using a min-heap of size k allows us to keep track of the k largest frequencies by always removing the smallest frequency when a larger one appears. This reduces memory usage and improves performance compared to sorting all elements or using a max-heap of all elements.