Top K Frequent Elements Using Heap in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Top K Frequent Elements with Min-Heap

What is the output of the following C# code that finds the top 2 frequent elements using a min-heap?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static IList<int> TopKFrequent(int[] nums, int k) {
        var freqMap = new Dictionary<int, int>();
        foreach (var num in nums) {
            freqMap[num] = freqMap.GetValueOrDefault(num, 0) + 1;
        }

        var minHeap = new SortedSet<(int freq, int val)>(Comparer<(int, int)>.Create((a, b) =>
            a.freq == b.freq ? a.val.CompareTo(b.val) : a.freq.CompareTo(b.freq)));

        foreach (var kvp in freqMap) {
            minHeap.Add((kvp.Value, kvp.Key));
            if (minHeap.Count > k) {
                minHeap.Remove(minHeap.Min);
            }
        }

        var result = new List<int>();
        foreach (var item in minHeap) {
            result.Add(item.val);
        }
        return result;
    }

    static void Main() {
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        var topK = TopKFrequent(nums, k);
        Console.WriteLine(string.Join(", ", topK));
    }
}

A [3, 2]

B [1, 2]

C [2, 1]

D [1, 3]

💡 Hint

Remember that the min-heap keeps the k elements with highest frequency, but the order in the heap is by frequency ascending.

The frequencies are: 1 -> 3 times, 2 -> 2 times, 3 -> 1 time. The min-heap keeps the top 2 frequent elements, which are 1 and 2. The SortedSet orders by frequency ascending, so the output list is [2, 1].

🧠 Conceptual

intermediate

Why Use a Min-Heap for Top K Frequent Elements?

Why is a min-heap preferred over a max-heap when finding the top K frequent elements?

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

B Because a min-heap sorts elements in descending order automatically.

C Because a max-heap cannot be implemented in C#.

D Because a min-heap stores all elements without size limit.

💡 Hint

Think about how to keep only the top k elements efficiently.

A min-heap keeps the smallest frequency element at the top, so when the heap size exceeds k, we remove the smallest frequency element. This way, the heap always contains the k most frequent elements.

🔧 Debug

advanced

Identify the Bug in Top K Frequent Elements Code

What error will the following code produce when run, and why? Code snippet: var freqMap = new Dictionary(); foreach (var num in nums) { freqMap[num] += 1; } // rest of code omitted for brevity

A InvalidOperationException due to heap misuse.

B No error, code runs correctly.

C SyntaxError due to missing semicolon.

D KeyNotFoundException because freqMap[num] is accessed before initialization.

💡 Hint

Check how dictionary keys are accessed and updated.

The code tries to increment freqMap[num] without checking if the key exists, causing a KeyNotFoundException on first access.

❓ Predict Output

advanced

Output of Top K Frequent Elements with Ties

What is the output of the following code when nums = {4,4,4,1,1,2,2,3} and k = 3?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static IList<int> TopKFrequent(int[] nums, int k) {
        var freqMap = new Dictionary<int, int>();
        foreach (var num in nums) {
            freqMap[num] = freqMap.GetValueOrDefault(num, 0) + 1;
        }

        var minHeap = new SortedSet<(int freq, int val)>(Comparer<(int, int)>.Create((a, b) =>
            a.freq == b.freq ? a.val.CompareTo(b.val) : a.freq.CompareTo(b.freq)));

        foreach (var kvp in freqMap) {
            minHeap.Add((kvp.Value, kvp.Key));
            if (minHeap.Count > k) {
                minHeap.Remove(minHeap.Min);
            }
        }

        var result = new List<int>();
        foreach (var item in minHeap) {
            result.Add(item.val);
        }
        return result;
    }

    static void Main() {
        int[] nums = {4,4,4,1,1,2,2,3};
        int k = 3;
        var topK = TopKFrequent(nums, k);
        Console.WriteLine(string.Join(", ", topK));
    }
}

A [4, 1, 2]

B [1, 2, 4]

C [2, 1, 4]

D [3, 2, 4]

💡 Hint

Check frequencies and how SortedSet orders elements with same frequency.

Frequencies: 4->3, 1->2, 2->2, 3->1. The top 3 are 4,1,2. SortedSet orders by frequency ascending, then value ascending, so output is [1, 2, 4].

🚀 Application

expert

Find Top K Frequent Words Using Heap

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

A

var freqMap = new Dictionary<string, int>();
foreach (var w in words) freqMap[w] = freqMap.GetValueOrDefault(w, 0) + 1;
var minHeap = new SortedSet<(int freq, string word)>(Comparer<(int, string)>.Create((a, b) =>
    a.freq == b.freq ? string.Compare(a.word, b.word) : a.freq.CompareTo(b.freq)));
foreach (var kvp in freqMap) {
    minHeap.Add((kvp.Value, kvp.Key));
    if (minHeap.Count > 2) minHeap.Remove(minHeap.Min);
}
var result = new List<string>();
foreach (var item in minHeap) result.Add(item.word);
result.Reverse();
return result;

B

var freqMap = new Dictionary<string, int>();
foreach (var w in words) freqMap[w] = freqMap.GetValueOrDefault(w, 0) + 1;
var minHeap = new SortedSet<(int freq, string word)>(Comparer<(int, string)>.Create((a, b) =>
    a.freq == b.freq ? string.Compare(b.word, a.word) : a.freq.CompareTo(b.freq)));
foreach (var kvp in freqMap) {
    minHeap.Add((kvp.Value, kvp.Key));
    if (minHeap.Count > 2) minHeap.Remove(minHeap.Min);
}
var result = new List<string>();
foreach (var item in minHeap) result.Add(item.word);
result.Reverse();
return result;

C

var freqMap = new Dictionary<string, int>();
foreach (var w in words) freqMap[w] = freqMap.GetValueOrDefault(w, 0) + 1;
var minHeap = new SortedSet<(int freq, string word)>(Comparer<(int, string)>.Create((a, b) =>
    a.freq == b.freq ? string.Compare(a.word, b.word) : b.freq.CompareTo(a.freq)));
foreach (var kvp in freqMap) {
    minHeap.Add((kvp.Value, kvp.Key));
    if (minHeap.Count > 2) minHeap.Remove(minHeap.Min);
}
var result = new List<string>();
foreach (var item in minHeap) result.Add(item.word);
return result;

D

var freqMap = new Dictionary<string, int>();
foreach (var w in words) freqMap[w] = freqMap.GetValueOrDefault(w, 0) + 1;
var minHeap = new SortedSet<(int freq, string word)>(Comparer<(int, string)>.Create((a, b) =>
    a.freq == b.freq ? string.Compare(b.word, a.word) : b.freq.CompareTo(a.freq)));
foreach (var kvp in freqMap) {
    minHeap.Add((kvp.Value, kvp.Key));
    if (minHeap.Count > 2) minHeap.Remove(minHeap.Min);
}
var result = new List<string>();
foreach (var item in minHeap) result.Add(item.word);
return result;

💡 Hint

Remember to sort by frequency ascending in min-heap and lex ascending for ties, then reverse the result.

To get top frequent words sorted by frequency descending and lex ascending, the min-heap comparator must order by frequency ascending and lex ascending. After extracting, reverse the list to get correct order.

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 efficiently keep track of the top K elements by frequency

D. To remove duplicates from the list

Solution

1. Step 1: Understand the role of a heap

   A heap is a special tree-based data structure that helps efficiently find and maintain the largest or smallest elements.

2. Step 2: Apply heap to the problem context

   In the Top K Frequent Elements problem, a heap helps keep track of the K elements with the highest frequency without sorting the entire list.

3. Final Answer:

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

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps top K elements efficiently without full sorting [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple list or array
• Ignoring frequency importance

2. Which of the following C# code snippets correctly declares a min-heap using SortedSet for integers?

easy

A. var minHeap = new Stack<int>();

B. var minHeap = new List<int>();

C. var minHeap = new Dictionary();

D. var minHeap = new SortedSet<int>();

Solution

1. Step 1: Identify data structure for min-heap

   A min-heap can be implemented using a SortedSet in C# because it keeps elements sorted automatically.

2. Step 2: Check code correctness

   var minHeap = new SortedSet<int>(); declares a SortedSet<int>, which acts like a min-heap by keeping smallest element accessible.

3. Final Answer:

   var minHeap = new SortedSet<int>(); -> Option D

4. Quick Check:

   SortedSet = min-heap structure [OK]

Hint: Use SortedSet for min-heap in C# [OK]

Common Mistakes:

• Using List instead of a heap structure
• Confusing Dictionary with heap
• Using Stack which is LIFO, not heap

3. What will be the output of the following C# code snippet that finds top 2 frequent elements?

int[] nums = {1,1,1,2,2,3};
int k = 2;
var freq = new Dictionary();
foreach(var num in nums) freq[num] = freq.GetValueOrDefault(num, 0) + 1;
var heap = new SortedSet<(int freq, int num)>();
foreach(var pair in freq) {
    heap.Add((pair.Value, pair.Key));
    if(heap.Count > k) heap.Remove(heap.Min);
}
var result = heap.Select(x => x.num).ToList();
Console.WriteLine(string.Join(", ", result));

medium

A. 2, 1

B. 1, 2

C. 1, 3

D. 3, 2

Solution

1. Step 1: Count frequencies

   Frequencies are: 1 -> 3 times, 2 -> 2 times, 3 -> 1 time.

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

   Heap keeps pairs (freq, num). It adds all pairs: (3,1), (2,2), (1,3). When size > 2, removes smallest freq (1,3). Leaving (2,2) and (3,1). SortedSet iterates in ascending order: (2,2), then (3,1).

3. Step 3: Output order

   Result list is created by selecting num from heap in ascending order of freq, so output is "2, 1".

4. Final Answer:

   2, 1 -> Option A

5. Quick Check:

   Top 2 frequent = 2, 1 [OK]

Hint: Keep heap size k, remove smallest freq when exceeded [OK]

Common Mistakes:

• Not removing smallest freq when heap size exceeds k
• Mixing element and frequency order
• Printing frequencies instead of elements

4. Identify the bug in this C# code snippet for top 1 frequent element:

int[] nums = {4,4,4,6,6,7};
int k = 1;
var freq = new Dictionary();
foreach(var num in nums) freq[num] = freq.GetValueOrDefault(num, 0) + 1;
var heap = new SortedSet<(int freq, int num)>();
foreach(var pair in freq) {
    heap.Add((pair.Value, pair.Key));
    if(heap.Count > k) heap.Remove(heap.Max);
}
var result = heap.Select(x => x.num).ToList();
Console.WriteLine(string.Join(", ", result));

medium

A. Removing heap.Max instead of heap.Min causes wrong elements removal

B. Dictionary initialization is incorrect

C. Using GetValueOrDefault causes runtime error

D. Heap should store only numbers, not frequency

Solution

1. Step 1: Understand heap removal logic

   Heap is a min-heap by frequency, so smallest freq is at Min, largest at Max.

2. Step 2: Identify incorrect removal

   Code removes heap.Max when size exceeds k, which removes the largest frequency element instead of smallest, causing wrong result.

3. Final Answer:

   Removing heap.Max instead of heap.Min causes wrong elements removal -> Option A

4. Quick Check:

   Remove heap.Min to keep top frequent [OK]

Hint: Remove heap.Min to keep top frequent elements [OK]

Common Mistakes:

• Removing heap.Max instead of heap.Min
• Confusing frequency and element order
• Not updating frequency dictionary correctly

5. Given the array nums = {5,3,1,1,1,3,73,1} and k = 2, which approach correctly returns the top 2 frequent elements using a heap in C#? A) Use a max-heap to store all elements and pop k times. B) Use a min-heap of size k to keep top frequent elements by frequency. C) Sort the array and pick last k elements. D) Use a queue to store elements and count frequencies later.

hard

A. Use a max-heap to store all elements and pop k times.

B. Use a min-heap of size k to keep top frequent elements by frequency.

C. Sort the array and pick last k elements.

D. Use a queue to store elements and count frequencies later.

Solution

1. Step 1: Understand frequency counting

   Count frequencies: 1 -> 4 times, 3 -> 2 times, 5 -> 1 time, 73 -> 1 time.

2. Step 2: Use min-heap of size k

   Use a min-heap to keep only top k frequent elements by frequency. When heap size exceeds k, remove smallest frequency element.

3. Step 3: Why other options fail

   A) Max-heap of all elements is inefficient. C) Sorting array doesn't group frequencies. D) Queue doesn't help frequency counting efficiently.

4. Final Answer:

   Use a min-heap of size k to keep top frequent elements by frequency. -> Option B

5. Quick Check:

   Min-heap size k = correct approach [OK]

Hint: Keep min-heap size k to track top frequent elements [OK]

Common Mistakes:

• Using max-heap for all elements wastes memory
• Sorting array ignores frequency counts
• Using queue without frequency map