Kth Largest Element Using Max Heap in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Largest Element Using Max Heap

What is the output of the following C# code that finds the 3rd largest element using a max heap?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int FindKthLargest(int[] nums, int k) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        foreach (var num in nums) {
            maxHeap.Enqueue(num, num);
        }
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.Dequeue();
        }
        return result;
    }

    static void Main() {
        int[] nums = {4, 1, 7, 3, 8, 5};
        int k = 3;
        Console.WriteLine(FindKthLargest(nums, k));
    }
}

A 7

B 3

C 4

D 5

💡 Hint

Remember the max heap returns the largest element first. Dequeue k times to get the kth largest.

The max heap orders elements from largest to smallest. Dequeuing three times returns the 3rd largest element, which is 5.

❓ Predict Output

intermediate

Output of Kth Largest Element with Duplicate Values

What will be printed by this C# code that finds the 4th largest element using a max heap with duplicates?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int FindKthLargest(int[] nums, int k) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        foreach (var num in nums) {
            maxHeap.Enqueue(num, num);
        }
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.Dequeue();
        }
        return result;
    }

    static void Main() {
        int[] nums = {2, 2, 3, 1, 4, 4};
        int k = 4;
        Console.WriteLine(FindKthLargest(nums, k));
    }
}

A 4

B 2

C 3

D 1

💡 Hint

Duplicates are treated as separate elements in the heap.

The max heap order is 4, 4, 3, 2, 2, 1. The 4th largest is the first 2.

🔧 Debug

advanced

Identify the Error in Kth Largest Element Code

What error will this C# code produce when trying to find the 2nd largest element using a max heap?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int FindKthLargest(int[] nums, int k) {
        var maxHeap = new PriorityQueue<int, int>();
        foreach (var num in nums) {
            maxHeap.Enqueue(num, num);
        }
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.Dequeue();
        }
        return result;
    }

    static void Main() {
        int[] nums = {5, 3, 8, 1};
        int k = 2;
        Console.WriteLine(FindKthLargest(nums, k));
    }
}

A Wrong output due to wrong priority order

B Output: 5

C Output: 3

D Output: 8

💡 Hint

Check how the PriorityQueue is constructed and what default priority order is.

PriorityQueue by default is a min heap. Without a custom comparer, it returns smallest first, so the code does not find kth largest correctly.

🧠 Conceptual

advanced

Why Use Max Heap for Kth Largest Element?

Which of the following best explains why a max heap is suitable for finding the kth largest element in an unsorted array?

A Because max heap allows quick access to the largest element, so removing the largest k times gives the kth largest.

B Because max heap always keeps the smallest element at the root, making it easy to find kth largest.

C Because max heap sorts the entire array automatically in ascending order.

D Because max heap stores elements in sorted order internally, so kth largest is at index k.

💡 Hint

Think about what element is at the root of a max heap.

Max heap root is the largest element. Removing it k times gives the kth largest element.

❓ Predict Output

expert

Output of Kth Largest Element Using Max Heap with Negative Numbers

What is the output of this C# code that finds the 2nd largest element using a max heap with negative numbers?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int FindKthLargest(int[] nums, int k) {
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        foreach (var num in nums) {
            maxHeap.Enqueue(num, num);
        }
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.Dequeue();
        }
        return result;
    }

    static void Main() {
        int[] nums = {-1, -3, -2, -4, 0};
        int k = 2;
        Console.WriteLine(FindKthLargest(nums, k));
    }
}

A 0

B -2

C -1

D -3

💡 Hint

Remember 0 is largest, then -1, then -2, etc.

The max heap order is 0, -1, -2, -3, -4. The 2nd largest is -1.

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Build a max heap from the array and extract the maximum element k times

B. Sort the array and pick the element at index k

C. Use a min heap to store all elements and extract the minimum k times

D. Traverse the array and count elements greater than k

Solution

1. Step 1: Build a max heap from the array

   A max heap is a binary tree where the parent node is always greater than its children. Building it from the array organizes elements so the largest is at the root.

2. Step 2: Extract the maximum element k times

   Extracting the root removes the largest element. Doing this k times leaves the kth largest element at the root after the last extraction.

3. Final Answer:

   Build max heap and extract max k times -> Option A

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to get kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Counting elements incorrectly

2. Which of the following is the correct C# syntax to create a max heap using PriorityQueue<int, int> where the largest element has the highest priority?

easy

A. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => a - b));

B. var maxHeap = new PriorityQueue();

C. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => b - a));

D. var maxHeap = new PriorityQueue(Comparer<int>.Default);

Solution

1. Step 1: Understand PriorityQueue default behavior

   By default, PriorityQueue<TElement, TPriority> in C# is a min heap based on priority, so smaller priority values come out first.

2. Step 2: Use custom comparer to reverse order for max heap

   To make it a max heap, we provide a comparer that reverses the order: b - a instead of a - b. This makes larger priorities come out first.

3. Final Answer:

   var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a)); -> Option C

4. Quick Check:

   Custom comparer reverses order for max heap [OK]

Hint: Use comparer (b - a) for max heap in PriorityQueue [OK]

Common Mistakes:

• Using default comparer which creates min heap
• Swapping comparer parameters incorrectly
• Not providing any comparer

3. What will be the output of the following C# code snippet that finds the 3rd largest element using a max heap?

int[] nums = {4, 1, 7, 3, 8, 5};
var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => b - a));
foreach (var num in nums) maxHeap.Enqueue(num, num);
int kthLargest = 0;
for (int i = 0; i < 3; i++) kthLargest = maxHeap.Dequeue();
Console.WriteLine(kthLargest);

medium

A. 7

B. 5

C. 4

D. 3

Solution

1. Step 1: Build max heap from array

   The max heap will organize elements so the largest is at the root: 8, 7, 5, 4, 3, 1.

2. Step 2: Extract max 3 times

   First dequeue: 8 (largest)
   Second dequeue: 7 (second largest)
   Third dequeue: 5 (third largest)

3. Final Answer:

   5 -> Option B

4. Quick Check:

   3rd largest element = 5 [OK]

Hint: Extract max 3 times; last extracted is 3rd largest [OK]

Common Mistakes:

• Confusing index with value
• Extracting fewer or more times
• Using min heap instead of max heap

4. The following code attempts to find the 2nd largest element using a max heap but throws an exception. What is the error?

int[] nums = {10, 20};
var maxHeap = new PriorityQueue();
foreach (var num in nums) maxHeap.Enqueue(num, num);
int kthLargest = 0;
for (int i = 0; i <= 2; i++) kthLargest = maxHeap.Dequeue();
Console.WriteLine(kthLargest);

medium

A. The loop runs one time too many causing an exception

B. PriorityQueue is not initialized with a comparer for max heap

C. The array has fewer elements than k

D. Enqueue method is used incorrectly

Solution

1. Step 1: Check loop bounds for dequeue

   The loop runs from 0 to 2 inclusive, which means 3 iterations. But the array has only 2 elements.

2. Step 2: Understand dequeue behavior

   After 2 dequeues, the heap is empty. The 3rd dequeue causes an InvalidOperationException because the heap is empty.

3. Final Answer:

   The loop runs one time too many causing an exception -> Option A

4. Quick Check:

   Loop runs 3 times but only 2 elements exist [OK]

Hint: Loop should run k times, not k+1 times [OK]

Common Mistakes:

• Using <= instead of < in loop
• Not checking array size before dequeue
• Ignoring exception from empty heap

5. Given a large array with many duplicate elements, which approach using a max heap is best to find the 4th largest unique element efficiently?

hard

A. Build a max heap from all elements and extract max 4 times

B. Use a min heap of size 4 to track largest unique elements

C. Sort the array and pick the 4th element from the end

D. Use a max heap but skip duplicates during extraction until 4 unique elements are found

Solution

1. Step 1: Understand duplicates affect kth largest unique element

   Simply extracting max 4 times may count duplicates multiple times, giving wrong result.

2. Step 2: Skip duplicates during extraction

   Extract max repeatedly, but ignore elements equal to previously extracted ones until 4 unique elements are found.

3. Step 3: Why other options are less efficient

   Sorting is O(n log n) and may be costly for large arrays. Using a min heap of size 4 does not handle duplicates well without extra checks.

4. Final Answer:

   Use a max heap but skip duplicates during extraction until 4 unique elements are found -> Option D

5. Quick Check:

   Skip duplicates while extracting max for unique kth largest [OK]

Hint: Skip duplicates while extracting max to find unique kth largest [OK]

Common Mistakes:

• Counting duplicates as separate largest elements
• Using min heap without uniqueness checks
• Sorting entire array unnecessarily