Top K Frequent Elements Using Heap in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a heap to find the top K frequent elements?

Use a heap to keep track of the K elements with the highest frequency by pushing elements and popping the least frequent when size exceeds K.

beginner

What type of heap is commonly used to solve the Top K Frequent Elements problem efficiently?

A min-heap is used to keep the smallest frequency element at the top, so when the heap size exceeds K, the least frequent element can be removed.

beginner

Why do we use a frequency map before using a heap in this problem?

The frequency map counts how many times each element appears, which helps us know the frequency to compare when adding elements to the heap.

intermediate

In JavaScript, which data structure can be used to implement a min-heap for this problem?

JavaScript does not have a built-in heap, so we can implement a min-heap using an array and helper functions to maintain heap properties.

intermediate

What is the time complexity of finding the top K frequent elements using a heap?

The time complexity is O(N log K), where N is the number of unique elements, because each element is pushed and popped from the heap of size K.

What data structure is first used to count element frequencies before using a heap?

A Hash map (object or Map)

B Array

C Stack

D Queue

A hash map is used to count how many times each element appears.

Which heap type helps efficiently keep track of the top K frequent elements?

A Max-heap

B Fibonacci heap

C Min-heap

D Binary search tree

A min-heap keeps the smallest frequency at the top, so we can remove less frequent elements when size exceeds K.

If the heap size exceeds K, what operation is performed?

A Add more elements

B Remove the least frequent element

C Remove the most frequent element

D Clear the heap

We remove the least frequent element to keep only the top K frequent elements.

What is the main benefit of using a heap over sorting all elements by frequency?

A Heap is faster when K is much smaller than N

B Heap uses less memory

C Heap is easier to implement

D Heap sorts elements alphabetically

Heap is faster because it only keeps track of K elements instead of sorting all N elements.

What is the output of the algorithm?

A All elements sorted by frequency

B Top K frequent elements sorted descending

C Top K frequent elements sorted ascending

D Top K frequent elements in any order

The algorithm returns the top K frequent elements but order is not guaranteed.

Explain step-by-step how to find the top K frequent elements using a heap.

Think about counting first, then using a small heap to keep only K elements.

Why is a min-heap preferred over a max-heap for this problem?

Consider which element you want to remove when the heap grows too big.

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 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 keep track of the top K frequent elements efficiently by always having the smallest frequency at the root, so less frequent elements can be removed quickly.

3. Final Answer:

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

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps smallest frequency on top for quick removal [OK]

Common Mistakes:

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

2. Which of the following is the correct way to create a min-heap in JavaScript using a priority queue for frequencies?

easy

A. const heap = new MinHeap(x => x.frequency);

B. const heap = new PriorityQueue(x => x.frequency);

C. const heap = new MinPriorityQueue({ priority: x => x.frequency });

D. const heap = new PriorityQueue({ compare: (a,b) => a.frequency - b.frequency });

Solution

1. Step 1: Identify correct syntax for min-heap in JavaScript

   Using the standard library or popular libraries, MinPriorityQueue with a priority function is the correct way.

2. Step 2: Check options for correct constructor and priority function

   const heap = new MinPriorityQueue({ priority: x => x.frequency }); uses new MinPriorityQueue({ priority: x => x.frequency }), which is the correct modern syntax.

3. Final Answer:

   const heap = new MinPriorityQueue({ priority: x => x.frequency }); -> Option C

4. Quick Check:

   MinPriorityQueue with priority function = const heap = new MinPriorityQueue({ priority: x => x.frequency }); [OK]

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

Common Mistakes:

• Using PriorityQueue without specifying min or max
• Passing compare function incorrectly
• Using non-existent MinHeap constructor

3. What will be the output of the following code snippet?

const nums = [1,1,1,2,2,3];
const k = 2;

// Frequency map
const freqMap = new Map();
for (const num of nums) {
  freqMap.set(num, (freqMap.get(num) || 0) + 1);
}

// Min heap simulation using array and sort
const heap = [];
for (const [num, freq] of freqMap.entries()) {
  heap.push([num, freq]);
  heap.sort((a, b) => a[1] - b[1]);
  if (heap.length > k) heap.shift();
}

const result = heap.map(x => x[0]);
console.log(result);

medium

A. [2, 3]

B. [2, 1]

C. [1, 3]

D. [3, 2]

Solution

1. Step 1: Build frequency map

   nums = [1,1,1,2,2,3] gives freqMap: {1:3, 2:2, 3:1}.

2. Step 2: Use min heap simulation to keep top 2 frequent

   Insert [1,3], heap=[(1,3)]; insert [2,2], heap=[(2,2),(1,3)] sorted by freq ascending; insert [3,1], heap=[(3,1),(2,2),(1,3)] then remove smallest freq (3,1), heap=[(2,2),(1,3)].

3. Final Answer:

   [2, 1] -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Not sorting heap after each insertion
• Removing wrong element when heap size exceeds k
• Confusing element and frequency order

4. Identify the bug in this code snippet for finding top K frequent elements:

const nums = [4,4,4,6,6,7];
const k = 2;
const freqMap = new Map();
for (const num of nums) {
  freqMap.set(num, freqMap.get(num) + 1);
}

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

const result = heap.map(x => x[0]);
console.log(result);

medium

A. freqMap.get(num) + 1 causes error when key is missing

B. Heap sorting should be descending, not ascending

C. k should be larger than array length

D. Using Map instead of Object for frequency map

Solution

1. Step 1: Check frequency map update logic

   freqMap.get(num) + 1 fails when num is not yet in map, because freqMap.get(num) returns undefined, causing NaN.

2. Step 2: Correct way to update frequency

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

3. Final Answer:

   freqMap.get(num) + 1 causes error when key is missing -> Option A

4. Quick Check:

   Undefined + 1 = NaN error [OK]

Hint: Always default missing map keys to 0 before adding [OK]

Common Mistakes:

• Not initializing frequency count
• Sorting heap in wrong order
• Misunderstanding Map vs Object usage

5. Given an array nums = [5,3,1,1,1,3,73,1] and k = 2, which approach correctly returns the top K frequent elements using a min-heap? Choose the best code snippet.

A:
const freqMap = new Map();
for (const n of nums) freqMap.set(n, (freqMap.get(n) || 0) + 1);
const heap = [];
for (const [num, freq] of freqMap.entries()) {
  heap.push([num, freq]);
  heap.sort((a,b) => a[1] - b[1]);
  if (heap.length > k) heap.shift();
}
return heap.map(x => x[0]);

B:
const freqMap = {};
for (const n of nums) freqMap[n] = freqMap[n] + 1;
const heap = new MinPriorityQueue({ priority: x => x[1] });
for (const [num, freq] of Object.entries(freqMap)) {
  heap.enqueue([num, freq]);
  if (heap.size() > k) heap.dequeue();
}
const result = [];
while (!heap.isEmpty()) result.push(heap.dequeue()[0]);
return result;

C:
const freqMap = new Map();
for (const n of nums) freqMap.set(n, freqMap.get(n) + 1);
const heap = [];
for (const [num, freq] of freqMap.entries()) {
  heap.push([num, freq]);
  heap.sort((a,b) => b[1] - a[1]);
  if (heap.length > k) heap.pop();
}
return heap.map(x => x[0]);

D:
const freqMap = new Map();
for (const n of nums) freqMap.set(n, (freqMap.get(n) || 0) + 1);
const heap = new MaxPriorityQueue({ priority: x => x[1] });
for (const [num, freq] of freqMap.entries()) {
  heap.enqueue([num, freq]);
  if (heap.size() > k) heap.dequeue();
}
const result = [];
while (!heap.isEmpty()) result.push(heap.dequeue()[0]);
return result;

hard

A. Option A is correct and uses array sort as min-heap simulation

B. Option B is correct using MinPriorityQueue with proper frequency map

C. Option C is correct using max-heap and popping largest frequency

D. Option D is correct using MaxPriorityQueue but removes wrong elements

Solution

1. Step 1: Verify frequency map in each option

   A: Uses Map with (get(n) || 0) + 1 -> correct. B: Object freqMap[n] = freqMap[n] + 1 -> undefined + 1 = NaN -> incorrect. C: Map.set(n, get(n) + 1) -> NaN -> incorrect. D: Map with || 0 -> correct.

2. Step 2: Verify heap logic for keeping top K largest frequencies

   Min-heap keeps size ≤ k by removing smallest freq. A: Sort ascending freq, shift smallest -> correct. B: MinPriorityQueue on freq, dequeue smallest -> correct logic. C: Sort descending, pop largest -> removes largest -> wrong. D: MaxPriorityQueue dequeues largest -> wrong.

3. Step 3: Overall correctness

   Frequencies: 1:4, 3:2, 5:1, 73:1. Top K: 1,3. Only A has correct freq map and heap logic, returns [3,1]. B,C fail on freq map; C,D wrong logic.

4. Final Answer:

   Option A is correct and uses array sort as min-heap simulation -> Option A

5. Quick Check:

   Correct freq + min-heap sim = Option A is correct and uses array sort as min-heap simulation [OK]

Hint: Use MinPriorityQueue with frequency map and size limit k [OK]

Common Mistakes:

• Not initializing frequency counts in object
• Using max-heap instead of min-heap for top K
• Using array sort instead of heap for efficiency