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

Time Complexity: Top K Frequent Elements Using Heap

O(n + u log k)

Understanding Time Complexity

We want to find the most frequent items in a list efficiently. Understanding time complexity helps us see how the solution scales when the list grows.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    count = Counter(nums)  # Count frequencies
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for freq, num in heap]
    

This code finds the k most frequent numbers in the list using a min-heap.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over unique numbers to push and pop from the heap.
• How many times: Once for each unique number in the list.

How Execution Grows With Input

As the list grows, counting frequencies takes longer, and managing the heap depends on unique numbers.

Input Size (n)	Approx. Operations
10	Counting ~10, Heap ops ~unique count
100	Counting ~100, Heap ops ~unique count
1000	Counting ~1000, Heap ops ~unique count

Pattern observation: Counting grows linearly with input size, heap operations grow with unique elements, which is usually less than total input.

Final Time Complexity

Time Complexity: O(n + u log k)

This means counting all elements takes time proportional to the list size, and managing the heap depends on the number of unique elements and k.

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, not all list items, and keep heap size limited to k, so heap operations depend on unique count and k, not total n.

Interview Connect

Understanding how to combine counting and heap operations shows you can handle data efficiently. This skill is useful for many real-world problems where you need top results quickly.

Self-Check

"What if we used a max-heap for all elements instead of a min-heap limited to size k? 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 efficiently keep track of the top k elements by frequency

B. To sort all elements in ascending order

C. To store elements without any order

D. To remove duplicates from the list

Solution

1. Step 1: Understand the problem goal

   The problem asks 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 frequent elements by maintaining a small structure of size k, allowing quick access to the smallest frequency among them.

3. Final Answer:

   To efficiently keep track of the top k elements by frequency -> Option A

4. Quick Check:

   Heap = Efficient top k tracking [OK]

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

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple list or set
• Assuming heap removes duplicates

2. Which of the following Python code snippets correctly creates a min-heap from a list freq_list using the heapq module?

easy

A. import heapq
heapq.makeheap(freq_list)

B. import heapq
heapq.heapify(freq_list)

C. import heapq
heapq.heap(freq_list)

D. import heapq
heapq.create(freq_list)

Solution

1. Step 1: Recall heapq module functions

   The heapq module provides heapify() to convert a list into a heap in-place.

2. Step 2: Identify correct function usage

   Only heapq.heapify(freq_list) is valid syntax to create a min-heap from a list.

3. Final Answer:

   import heapq heapq.heapify(freq_list) -> Option B

4. Quick Check:

   heapify() creates heap [OK]

Hint: Use heapq.heapify() to build a heap from list [OK]

Common Mistakes:

• Using non-existent heapq functions
• Confusing heapify with sorting
• Missing import statement

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

import heapq
nums = [1,1,1,2,2,3]
count = {}
for n in nums:
    count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
    heapq.heappush(heap, (freq, num))
result = []
for _ in range(2):
    result.append(heapq.heappop(heap)[1])
print(result)

medium

A. [1, 2]

B. [2, 3]

C. [1, 3]

D. [3, 2]

Solution

1. Step 1: Count frequencies of elements

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

2. Step 2: Push (freq, num) into min-heap and pop twice

   Heap contains (3,1), (2,2), (1,3). Popping twice removes smallest freq first: (1,3), then (2,2). So result = [3, 2].

3. Final Answer:

   [3, 2] -> Option D

4. Quick Check:

   Lowest freq elements popped first = [3, 2] [OK]

Hint: Min-heap pops smallest frequency first [OK]

Common Mistakes:

• Assuming heap pops highest frequency first
• Mixing up element and frequency order
• Not counting frequencies correctly

4. Identify the error in the following code snippet that tries to find the top 2 frequent elements:

import heapq
nums = [4,4,4,5,5,6]
count = {}
for n in nums:
    count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
    heapq.heappush(heap, (num, freq))
result = []
for _ in range(2):
    result.append(heapq.heappop(heap)[1])
print(result)

medium

A. The range in the last loop should be 3 instead of 2

B. The count dictionary is not updated correctly

C. The tuple pushed to heap should be (freq, num), not (num, freq)

D. heapq.heappush is used incorrectly; should use heapq.push

Solution

1. Step 1: Check tuple order pushed to heap

   The heap is a min-heap by first tuple element. Pushing (num, freq) orders by num, not frequency.

2. Step 2: Correct tuple order for frequency sorting

   To get top frequent elements, push (freq, num) so heap orders by frequency.

3. Final Answer:

   The tuple pushed to heap should be (freq, num), not (num, freq) -> Option C

4. Quick Check:

   Heap order depends on first tuple element [OK]

Hint: Push (frequency, element) tuples to heap [OK]

Common Mistakes:

• Swapping frequency and element in tuple
• Using wrong heapq function name
• Incorrect loop range for popping

5. Given the list nums = [2,3,2,4,3,3,5,5,5,5] and k = 2, which of the following code snippets correctly returns the top k frequent elements using a heap?

hard

A. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
if len(heap) < k:
heapq.heappush(heap, (freq, num))
else:
if freq > heap[0][0]:
heapq.heapreplace(heap, (freq, num))
result = [num for freq, num in heap]
print(result)

B. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
heapq.heappush(heap, (num, freq))
result = [heapq.heappop(heap)[1] for _ in range(k)]
print(result)

C. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
heapq.heappush(heap, (-freq, num))
result = [heapq.heappop(heap)[0] for _ in range(k)]
print(result)

D. import heapq
count = {}
for n in nums:
count[n] = count.get(n, 0) + 1
heap = []
for num, freq in count.items():
if freq < k:
heapq.heappush(heap, (freq, num))
result = [num for freq, num in heap]
print(result)

Solution

1. Step 1: Understand the problem and approach

   We want top k frequent elements using a min-heap of size k to keep track of highest frequencies.

2. Step 2: Analyze each option

   import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): if len(heap) < k: heapq.heappush(heap, (freq, num)) else: if freq > heap[0][0]: heapq.heapreplace(heap, (freq, num)) result = [num for freq, num in heap] print(result) correctly pushes (freq, num) and maintains heap size k, replacing smallest freq when a bigger freq is found. import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): heapq.heappush(heap, (num, freq)) result = [heapq.heappop(heap)[1] for _ in range(k)] print(result) pushes (num, freq) which is wrong order. import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): heapq.heappush(heap, (-freq, num)) result = [heapq.heappop(heap)[1] for _ in range(k)] print(result) uses negative freq but does not maintain heap size k properly. import heapq count = {} for n in nums: count[n] = count.get(n, 0) + 1 heap = [] for num, freq in count.items(): if freq < k: heapq.heappush(heap, (freq, num)) result = [num for freq, num in heap] print(result) pushes only if freq < k which is incorrect logic.

3. Final Answer:

   Option A code correctly returns top k frequent elements -> Option A

4. Quick Check:

   Min-heap size k with freq as key [OK]

Hint: Maintain min-heap size k with (freq, num) tuples [OK]

Common Mistakes:

• Pushing wrong tuple order to heap
• Not limiting heap size to k
• Using negative frequencies without proper logic