Kth Smallest Element Using Min Heap in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

What is the output of the following C# code that uses a min heap to find the 3rd smallest element?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;
        var minHeap = new SortedSet<(int val, int idx)>();
        for (int i = 0; i < arr.Length; i++) {
            minHeap.Add((arr[i], i));
        }
        int kthSmallest = 0;
        for (int i = 0; i < k; i++) {
            var min = minHeap.Min;
            kthSmallest = min.val;
            minHeap.Remove(min);
        }
        Console.WriteLine(kthSmallest);
    }
}

A 7

B 3

C 4

D 10

💡 Hint

Remember the min heap always gives the smallest element first.

The sorted set acts like a min heap here. The elements in order are 3, 4, 7, 10, 15, 20. The 3rd smallest is 7.

🧠 Conceptual

intermediate

Understanding Min Heap Behavior

If you want to find the 5th smallest element using a min heap, which of these steps is NOT required?

A Insert all elements into the min heap

B Keep track of the last extracted element

C Extract the minimum element 5 times

D Sort the entire array before inserting into the heap

💡 Hint

Min heap automatically keeps elements sorted partially.

Sorting the entire array before inserting is unnecessary because the min heap structure maintains order for extraction.

🔧 Debug

advanced

Identify the Error in Kth Smallest Element Code

What error will this code produce when trying to find the 2nd smallest element?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] arr = {5, 3};
        int k = 2;
        var minHeap = new SortedSet<int>();
        foreach (var num in arr) {
            minHeap.Add(num);
        }
        int kthSmallest = 0;
        for (int i = 0; i < k; i++) {
            kthSmallest = minHeap.Min;
            minHeap.Remove(kthSmallest);
        }
        Console.WriteLine(kthSmallest);
    }
}

A InvalidOperationException: Set is empty

B Output is 5

C Output is 3

D Compilation error

💡 Hint

Check the loop boundary for extracting elements.

The loop runs k+1 times (3 times for k=2) but only 2 elements exist. The last iteration tries to access Min of empty set causing InvalidOperationException.

❓ Predict Output

advanced

Output of Partial Min Heap Extraction

What is the output of this code snippet that extracts the 1st and 2nd smallest elements from a min heap?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] arr = {12, 3, 5, 7, 19};
        var minHeap = new SortedSet<int>(arr);
        int first = minHeap.Min;
        minHeap.Remove(first);
        int second = minHeap.Min;
        minHeap.Remove(second);
        Console.WriteLine(first + "," + second);
    }
}

A 3,7

B 3,5

C 12,3

D 5,7

💡 Hint

Min heap always returns the smallest element first.

The smallest element is 3, then after removing it, the next smallest is 5.

🚀 Application

expert

Kth Smallest Element in a Stream Using Min Heap

You receive a stream of integers and want to find the 4th smallest element at any time using a min heap. Which approach is correct?

A Keep a min heap of size 4, add elements, and remove min when size exceeds 4; the root is the 4th smallest

B Sort all elements each time a new element arrives and pick the 4th element

C Keep a max heap of size 4, add elements, and remove max when size exceeds 4; the root is the 4th smallest

D Keep all elements in a min heap and extract min 4 times when needed

💡 Hint

To track kth smallest efficiently, keep only k elements in a heap.

A max heap of size k keeps the k smallest elements seen so far. The root is the largest among them, which is the kth smallest overall.

Practice

1. What does a min heap guarantee about its root element when used to find the kth smallest element?

easy

A. The root is the average of all elements in the heap

B. The root is always the largest element in the heap

C. The root is the kth smallest element directly

D. The root is always the smallest element in the heap

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so the root is the minimum of all elements in the heap.

2. Step 2: Relation to kth smallest element

   By removing the root k-1 times, the root then becomes the kth smallest element.

3. Final Answer:

   The root is always the smallest element in the heap -> Option D

4. Quick Check:

   Min heap root = smallest element [OK]

Hint: Min heap root is always smallest element [OK]

Common Mistakes:

• Thinking root is largest element
• Assuming root is directly kth smallest without removals
• Confusing min heap with max heap

2. Which of the following is the correct way to initialize a min heap in C# using PriorityQueue<int, int> to find the kth smallest element?

easy

A. var minHeap = new PriorityQueue();

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

C. var minHeap = new PriorityQueue();

D. var minHeap = new PriorityQueue();

Solution

1. Step 1: Check PriorityQueue constructor syntax

   In C#, PriorityQueue<TElement, TPriority> requires two type parameters: element type and priority type. For integers, both are int.

2. Step 2: Validate options

   var minHeap = new PriorityQueue(); correctly uses PriorityQueue<int, int>. Options B, C, and D have incorrect or missing type parameters.

3. Final Answer:

   var minHeap = new PriorityQueue<int, int>(); -> Option C

4. Quick Check:

   Correct generic types for min heap = var minHeap = new PriorityQueue(); [OK]

Hint: Use PriorityQueue for min heap [OK]

Common Mistakes:

• Using only one generic type parameter
• Swapping element and priority types
• Using string instead of int for priority

3. What is the output of the following C# code snippet that uses a min heap to find the 3rd smallest element?

var nums = new int[] {7, 10, 4, 3, 20, 15};
var minHeap = new PriorityQueue();
foreach(var num in nums) {
    minHeap.Enqueue(num, num);
}
int kthSmallest = 0;
for(int i = 0; i < 3; i++) {
    kthSmallest = minHeap.Dequeue();
}
Console.WriteLine(kthSmallest);

medium

A. 7

B. 4

C. 10

D. 3

Solution

1. Step 1: Insert all elements into min heap

   Elements inserted: 7, 10, 4, 3, 20, 15. Min heap root is smallest element.

2. Step 2: Remove root 3 times to get 3rd smallest

   Dequeue order: 3 (1st), 4 (2nd), 7 (3rd). So, kthSmallest after 3 dequeues is 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   3rd smallest in array = 7 [OK]

Hint: Dequeue k times from min heap to get kth smallest [OK]

Common Mistakes:

• Assuming kth smallest is the root without dequeues
• Confusing array order with heap order
• Off-by-one error in loop count

4. Identify the error in this code snippet that tries to find the 2nd smallest element using a min heap:

var nums = new int[] {5, 3, 8, 1};
var minHeap = new PriorityQueue();
foreach(var num in nums) {
    minHeap.Enqueue(num);
}
int secondSmallest = minHeap.Dequeue();
secondSmallest = minHeap.Dequeue();
Console.WriteLine(secondSmallest);

medium

A. Missing priority argument in Enqueue method

B. Using Dequeue twice is incorrect

C. Array initialization syntax is wrong

D. PriorityQueue cannot be used for integers

Solution

1. Step 1: Check Enqueue method usage

   The PriorityQueue<TElement, TPriority> requires two arguments for Enqueue: element and priority. Here only element is passed.

2. Step 2: Identify correct usage

   Correct call is minHeap.Enqueue(num, num); to use element as priority.

3. Final Answer:

   Missing priority argument in Enqueue method -> Option A

4. Quick Check:

   Enqueue needs element and priority [OK]

Hint: Enqueue needs element and priority both [OK]

Common Mistakes:

• Passing only one argument to Enqueue
• Confusing Dequeue count
• Wrong array syntax

5. Given a large array with possible duplicate values, which approach using a min heap is best to find the 4th smallest unique element efficiently?

hard

A. Insert all elements into min heap and dequeue 4 times

B. Insert unique elements into min heap, then dequeue 4 times

C. Sort the array and pick the 4th element directly

D. Use a max heap of size 4 to track smallest unique elements

Solution

1. Step 1: Understand duplicates impact

   Duplicates cause incorrect counting if all elements are inserted. We want unique elements only.

2. Step 2: Use a set to filter unique elements before min heap

   Insert only unique elements into min heap, then dequeue 4 times to get 4th smallest unique element.

3. Final Answer:

   Insert unique elements into min heap, then dequeue 4 times -> Option B

4. Quick Check:

   Filter duplicates before heap for unique kth smallest [OK]

Hint: Filter duplicates before heap to find unique kth smallest [OK]

Common Mistakes:

• Ignoring duplicates causing wrong kth element
• Using max heap incorrectly for this problem
• Sorting entire array when heap is more efficient