Why Kth Largest Element Using Max Heap in DSA Typescript?

The Big Idea

What if you could find the 5th biggest number without sorting the whole list?

The Scenario

Imagine you have a huge list of exam scores and you want to find the 5th highest score. You try to scan the list again and again to find the top scores manually.

The Problem

Manually scanning the list multiple times is slow and tiring. You might miss scores or make mistakes counting. It takes too long when the list is very big.

The Solution

Using a max heap, you can quickly find the largest scores one by one. The heap keeps the biggest scores easy to find, so you can jump straight to the 5th largest without checking everything again.

Before vs After

✗ Before

let scores = [90, 85, 100, 70, 95];
// Find max, remove it, repeat 5 times
for (let i = 0; i < 5; i++) {
  let max = Math.max(...scores);
  scores = scores.filter(s => s !== max);
}

✓ After

let maxHeap = new MaxHeap(scores);
for (let i = 1; i < 5; i++) {
  maxHeap.extractMax();
}
let kthLargest = maxHeap.extractMax();

What It Enables

You can efficiently find the kth largest value in large data sets without sorting everything.

Real Life Example

Companies use this to find the top 10 highest sales days quickly from millions of records.

Key Takeaways

Manual searching is slow and error-prone.

Max heap organizes data to find largest elements fast.

This method saves time and effort for big lists.

Practice

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

easy

A. Use a hash map to count frequencies and find the kth largest.

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

C. Build a min heap and extract the minimum element k times.

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

Solution

1. Step 1: Understand max heap property

   A max heap always keeps the largest element at the root, so extracting the root gives the current largest element.

2. Step 2: Extract max k times

   By removing the root k times, the last extracted element is the kth largest.

3. Final Answer:

   Build a max heap and extract max k times -> Option D

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 instead of using heap
• Extracting fewer or more than k times

2. Which of the following TypeScript code snippets correctly creates a max heap from an array nums?

easy

A. const maxHeap = new MaxHeap(nums);

B. const maxHeap = new Heap(nums, (a, b) => a - b);

C. const maxHeap = new Heap(nums, (a, b) => b - a);

D. const maxHeap = new Heap(nums);

Solution

1. Step 1: Understand heap comparator

   To create a max heap, the comparator should order elements so that larger values come first, i.e., (a, b) => b - a.

2. Step 2: Check options

   const maxHeap = new Heap(nums, (a, b) => b - a); uses (a, b) => b - a, which correctly creates a max heap.

3. Final Answer:

   const maxHeap = new Heap(nums, (a, b) => b - a); -> Option C

4. Quick Check:

   Comparator b - a = max heap [OK]

Hint: Use comparator (a, b) => b - a for max heap [OK]

Common Mistakes:

• Using default comparator which creates min heap
• Reversing comparator incorrectly
• Assuming new MaxHeap() exists without comparator

3. What is the output of the following TypeScript code?

const nums = [3, 1, 5, 12, 2, 11];
const k = 3;
const maxHeap = new Heap(nums, (a, b) => b - a);
let kthLargest = null;
for (let i = 0; i < k; i++) {
  kthLargest = maxHeap.extract();
}
console.log(kthLargest);

medium

A. 5

B. 11

C. 3

D. 12

Solution

1. Step 1: Build max heap from array

   Max heap order: root is largest element. Initial max is 12, then 11, then 5.

2. Step 2: Extract max k=3 times

   Extract 1: 12, Extract 2: 11, Extract 3: 5. So kthLargest is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   3rd largest in [3,1,5,12,2,11] = 5 [OK]

Hint: Extract max k times; last extracted is kth largest [OK]

Common Mistakes:

• Confusing 3rd largest with 3rd smallest
• Extracting fewer than k times
• Not building max heap correctly

4. Identify the bug in this TypeScript code that tries to find the kth largest element using a max heap:

const nums = [7, 10, 4, 3, 20, 15];
const k = 4;
const maxHeap = new Heap(nums, (a, b) => b - a);
let kthLargest = null;
for (let i = 0; i <= k; i++) {
  kthLargest = maxHeap.extract();
}
console.log(kthLargest);

medium

A. The comparator is wrong; should be (a, b) => a - b.

B. The loop runs one extra time; should be i < k not i <= k.

C. The heap is not built correctly from the array.

D. The variable kthLargest should be initialized to 0.

Solution

1. Step 1: Check loop condition

   The loop runs from i = 0 to i = k inclusive, so it runs k+1 times.

2. Step 2: Correct loop to run exactly k times

   It should run k times, so condition must be i < k.

3. Final Answer:

   Loop runs one extra time; should be i < k -> Option B

4. Quick Check:

   Loop runs k times to extract kth largest [OK]

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

Common Mistakes:

• Using <= instead of < in loop
• Wrong comparator for max heap
• Initializing variables incorrectly

5. Given a large array nums with 1 million elements, which approach is most efficient to find the kth largest element when k is small (e.g., 10)?

hard

A. Build a min heap of size k and iterate through nums to maintain it.

B. Sort the entire array and pick the element at index length - k.

C. Use a hash map to count frequencies and find the kth largest.

D. Build a max heap of all elements and extract max k times.

Solution

1. Step 1: Analyze time complexity of building max heap

   Building max heap of 1 million elements is O(n), extracting k times is O(k log n), which is costly.

2. Step 2: Use min heap of size k

   Maintain a min heap of size k while iterating. This keeps top k largest elements efficiently in O(n log k).

3. Step 3: Compare with sorting

   Sorting entire array is O(n log n), slower than min heap approach for small k.

4. Final Answer:

   Build a min heap of size k and maintain it while iterating -> Option A

5. Quick Check:

   Min heap size k = efficient for small k [OK]

Hint: Use min heap of size k for large arrays and small k [OK]

Common Mistakes:

• Building max heap of entire array for large data
• Sorting entire array unnecessarily
• Ignoring heap size optimization