Kth Largest Element Using Max Heap in DSA C# - Time & Space Complexity

Time Complexity: Kth Largest Element Using Max Heap

O(n log n + k log n)

Understanding Time Complexity

We want to understand how long it takes to find the kth largest number using a max heap.

How does the time needed grow when the list of numbers gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int FindKthLargest(int[] nums, int k) {
    var maxHeap = new PriorityQueue<int, int>();
    foreach (var num in nums) {
        maxHeap.Enqueue(num, -num); // max heap by using negative priority
    }
    int result = 0;
    for (int i = 0; i < k; i++) {
        result = maxHeap.Dequeue();
    }
    return result;
}
    

This code builds a max heap from the array and removes the largest element k times to find the kth largest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding all elements to the max heap and removing the top element k times.
• How many times: Inserting n elements once each, then removing k elements once each.

How Execution Grows With Input

Each insertion and removal takes time related to the heap size.

Input Size (n)	Approx. Operations
10	About 10 insertions + k removals, each ~log 10 steps
100	About 100 insertions + k removals, each ~log 100 steps
1000	About 1000 insertions + k removals, each ~log 1000 steps

Pattern observation: Operations grow roughly with n times log n, plus k times log n, which is mostly driven by n.

Final Time Complexity

Time Complexity: O(n log n + k log n)

This means the time needed grows a bit faster than the number of elements because each insertion and removal takes extra steps related to the heap size.

Common Mistake

[X] Wrong: "Building the heap takes only O(n) time, so the whole process is O(n)."

[OK] Correct: While building a heap can be done in O(n), here we insert elements one by one, each taking O(log n), so total insertion is O(n log n). Also, removing k elements adds more O(k log n) time.

Interview Connect

Understanding this time complexity helps you explain why heap-based solutions are efficient and when they are suitable compared to sorting or other methods.

Self-Check

"What if we used a min heap of size k instead of a max heap of size n? How would the time complexity change?"

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