Top K Frequent Elements Using Heap in DSA Javascript - Time & Space Complexity

Time Complexity: Top K Frequent Elements Using Heap

O(n log k)

Understanding Time Complexity

We want to understand how the time needed grows when finding the top K frequent elements using a heap.

How does the work change as the list of numbers gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const topKFrequent = (nums, k) => {
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

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

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

This code counts how often each number appears, then keeps the top K numbers with the highest counts using a small heap.

Identify Repeating Operations

Look at the parts that repeat work:

• Primary operation: Loop over all numbers to count frequency (once).
• Secondary operation: Loop over unique numbers to build and maintain the heap.
• Dominant operation: Sorting the heap inside the loop, which happens for each unique number.

How Execution Grows With Input

As the input list grows, the number of unique numbers also grows, affecting the heap operations.

Input Size (n)	Approx. Operations
10	Counting: 10 steps, Heap ops: ~10 * log(k)
100	Counting: 100 steps, Heap ops: ~100 * log(k)
1000	Counting: 1000 steps, Heap ops: ~1000 * log(k)

Pattern observation: Counting grows linearly with input size, heap operations grow linearly with unique numbers times log of k.

Final Time Complexity

Time Complexity: O(n log k)

This means the time grows mostly with the input size times the log of k, which is usually much smaller than n.

Common Mistake

[X] Wrong: "Sorting the entire list of numbers is needed to find top K."

[OK] Correct: Sorting all numbers would take much longer. Using a heap keeps only the top K, saving time.

Interview Connect

Understanding how to use heaps to find top K elements efficiently is a valuable skill that shows you can handle large data smartly.

Self-Check

"What if we used a max heap instead of a min heap? How would the time complexity change?"

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