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

Time Complexity: Top K Frequent Elements Using Heap

O(n + m 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 input list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 heap = new MinHeap<[number, number]>((a, b) => a[1] - b[1]);
  for (const [num, freq] of freqMap) {
    heap.push([num, freq]);
    if (heap.size() > k) heap.pop();
  }

  return heap.toArray().map(([num]) => num);
}
    

This code counts how often each number appears, then uses a small heap to keep only the top K frequent numbers.

Identify Repeating Operations

• Primary operation: Loop over all numbers to count frequency, then loop over unique numbers to push into the heap.
• How many times: First loop runs n times (n = length of input), second loop runs m times (m = number of unique numbers).

How Execution Grows With Input

As the input size grows, counting frequencies grows linearly. Adding to the heap grows with unique numbers and heap size k.

Input Size (n)	Approx. Operations
10	~10 + 10 * log k
100	~100 + m * log k (m ≤ 100)
1000	~1000 + m * log k (m ≤ 1000)

Pattern observation: Counting grows directly with n, heap operations grow with unique count m but only logarithmically with k.

Final Time Complexity

Time Complexity: O(n + m log k)

This means the time grows mostly with input size n and the number of unique elements m times the small heap operations.

Common Mistake

[X] Wrong: "The heap operations take O(n log n) because we push all elements into the heap."

[OK] Correct: We only push unique elements (m), and the heap size is limited to k, so each push/pop is O(log k), not O(log n).

Interview Connect

Understanding this complexity helps you explain efficient use of heaps and maps, a common pattern in real problems.

Self-Check

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