Top K Frequent Elements Using Heap in DSA Python - 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 Python code that finds the top 2 frequent elements using a min-heap?

DSA Python

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    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]

print(sorted(top_k_frequent([1,1,1,2,2,3], 2)))

A [1, 2, 3]

B [1, 3]

C [2, 3]

D [1, 2]

💡 Hint

Remember the min-heap keeps the k largest frequencies by popping the smallest when size exceeds k.

The frequencies are {1:3, 2:2, 3:1}. The min-heap keeps top 2 frequencies, so elements 1 and 2 remain.

🧠 Conceptual

intermediate

Understanding Heap Usage in Top K Frequent Elements

Why do we use a min-heap instead of a max-heap to find the top K frequent elements efficiently?

A Because a min-heap keeps the smallest frequency at the top, allowing easy removal when size exceeds k.

B Because a max-heap sorts elements in ascending order automatically.

C Because min-heaps are faster to implement than max-heaps in Python.

D Because max-heaps cannot be used with frequency counts.

💡 Hint

Think about how to keep only the k largest frequencies in a heap of size k.

Using a min-heap of size k allows us to remove the smallest frequency when the heap grows larger than k, keeping only the top k frequent elements.

🔧 Debug

advanced

Identify the Error in Top K Frequent Elements Code

What error does the following code produce when run, and why? import heapq from collections import Counter def top_k_frequent(nums, k): count = Counter(nums) heap = [] for num, freq in count.items(): heapq.heappush(heap, (num, freq)) if len(heap) > k: heapq.heappop(heap) return [num for num, freq in heap] print(top_k_frequent([1,1,1,2,2,3], 2))

DSA Python

import heapq
from collections import Counter

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

print(top_k_frequent([1,1,1,2,2,3], 2))

A The code raises a TypeError because heapq cannot push tuples.

B The code raises a KeyError because Counter keys are accessed incorrectly.

C The output is incorrect because frequencies and numbers are swapped in the heap, so the heap does not keep top frequencies.

D The code runs correctly and outputs [1, 2].

💡 Hint

Check the order of elements pushed into the heap and what heapq compares.

Heapq compares the first tuple element. Swapping num and freq causes the heap to order by num, not frequency, so it does not keep top frequencies.

❓ Predict Output

advanced

Output of Top K Frequent Elements with Equal Frequencies

What is the output of this code when multiple elements have the same frequency?

DSA Python

import heapq
from collections import Counter

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

print(top_k_frequent([4,4,1,1,2,2,3], 2))

A [2, 3]

B [1, 4]

C [3, 4]

D [1, 2]

💡 Hint

Check frequencies: 4,1,2 appear twice; 3 appears once. The heap keeps top 2 frequencies.

Frequencies: 4:2, 1:2, 2:2, 3:1. The heap keeps two elements with frequency 2. The min-heap pops the smallest frequency when size > k, so 3 is removed. The remaining are 1 and 4 (or 2 and 4 or 1 and 2). The heap order depends on insertion order but final sorted output is [1,4].

🚀 Application

expert

Find Top K Frequent Words Using Heap

Given a list of words, which code snippet correctly returns the top 3 frequent words sorted by frequency descending and then alphabetically ascending?

A

from collections import Counter
import heapq

def top_k_words(words, k):
    count = Counter(words)
    heap = []
    for word, freq in count.items():
        heapq.heappush(heap, (-freq, word))
    result = []
    for _ in range(k):
        result.append(heapq.heappop(heap)[1])
    return result

print(top_k_words(['apple','banana','apple','orange','banana','apple','kiwi'], 3))

B

from collections import Counter
import heapq

def top_k_words(words, k):
    count = Counter(words)
    heap = []
    for word, freq in count.items():
        heapq.heappush(heap, (freq, word))
        if len(heap) > k:
            heapq.heappop(heap)
    return [word for freq, word in sorted(heap, key=lambda x: (-x[0], x[1]))]

print(top_k_words(['apple','banana','apple','orange','banana','apple','kiwi'], 3))

C

from collections import Counter
import heapq

def top_k_words(words, k):
    count = Counter(words)
    heap = []
    for word, freq in count.items():
        heapq.heappush(heap, (-freq, word))
        if len(heap) > k:
            heapq.heappop(heap)
    return [word for freq, word in sorted(heap, key=lambda x: (x[0], x[1]))]

print(top_k_words(['apple','banana','apple','orange','banana','apple','kiwi'], 3))

D

from collections import Counter
import heapq

def top_k_words(words, k):
    count = Counter(words)
    heap = []
    for word, freq in count.items():
        heapq.heappush(heap, (freq, word))
    result = []
    for _ in range(k):
        result.append(heapq.heappop(heap)[1])
    return result

print(top_k_words(['apple','banana','apple','orange','banana','apple','kiwi'], 3))

💡 Hint

Use negative frequency to simulate max-heap and pop k times to get top k words.

Option A uses negative frequency to create a max-heap, then pops k times to get top k frequent words sorted by frequency descending and alphabetically ascending.

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