Kth Largest Element Using Max Heap in DSA Typescript

Mental Model

A max heap keeps the largest element at the top, so removing the top element k times gives the kth largest.

Analogy: Imagine a pile of books stacked so the biggest book is always on top. Taking the top book off repeatedly lets you find the kth biggest book.

       [10]
      /     \
   [7]       [9]
  /   \     /   \
[3]  [5]  [8]  [4]

Dry Run Walkthrough

Input: array: [3, 10, 5, 7, 9, 8, 4], k = 3

Goal: Find the 3rd largest element in the array using a max heap

Step 1: Build max heap from array

       [10]
      /     \
   [9]       [8]
  /   \     /   \
[3]  [7]  [5]  [4]

Why: We need the largest element at the root to extract it easily

Step 2: Extract max (10), remove root and reheapify

       [9]
      /     \
   [7]       [8]
  /   \     /   
[3]  [4]  [5]  null

Why: Removing the largest element moves us closer to the kth largest

Step 3: Extract max (9), remove root and reheapify

       [8]
      /     \
   [7]       [5]
  /   \     /   
[3]  [4]  null  null

Why: Second largest removed, next largest is now root

Step 4: Extract max (8), this is the 3rd largest element

       [7]
      /     \
   [4]       [5]
  /   \     /   
[3]  null  null  null

Why: The root now is the kth largest element extracted

Result:

3rd largest element is 8

Annotated Code

DSA Typescript

class MaxHeap {
  heap: number[] = [];

  constructor(arr: number[]) {
    this.heap = arr;
    this.buildMaxHeap();
  }

  buildMaxHeap() {
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapify(i);
    }
  }

  heapify(i: number) {
    const n = this.heap.length;
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && this.heap[left] > this.heap[largest]) {
      largest = left;
    }

    if (right < n && this.heap[right] > this.heap[largest]) {
      largest = right;
    }

    if (largest !== i) {
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      this.heapify(largest);
    }
  }

  extractMax(): number | null {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapify(0);
    return max;
  }
}

function findKthLargest(arr: number[], k: number): number | null {
  const maxHeap = new MaxHeap(arr);
  let kthLargest: number | null = null;
  for (let i = 0; i < k; i++) {
    kthLargest = maxHeap.extractMax();
  }
  return kthLargest;
}

// Driver code
const arr = [3, 10, 5, 7, 9, 8, 4];
const k = 3;
const result = findKthLargest(arr, k);
console.log(`${k}th largest element is ${result}`);

for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) { this.heapify(i); }

build max heap by heapifying from bottom non-leaf nodes up

if (left < n && this.heap[left] > this.heap[largest]) { largest = left; }

find largest among node and left child

if (right < n && this.heap[right] > this.heap[largest]) { largest = right; }

find largest among current largest and right child

if (largest !== i) { swap and heapify(largest); }

swap and continue heapify to maintain max heap property

const max = this.heap[0]; this.heap[0] = this.heap.pop(); this.heapify(0); return max;

extract max root, replace with last element, then heapify root

for (let i = 0; i < k; i++) { kthLargest = maxHeap.extractMax(); }

extract max k times to get kth largest

Output

3th largest element is 8

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each extract max takes O(log n) repeated k times

Space: O(n) because the heap stores all elements

vs Alternative: Sorting the array takes O(n log n), which is slower than building a heap plus k extractions when k is small

Edge Cases

k is larger than array length

extractMax returns null after heap is empty, final result is null

DSA Typescript

if (this.heap.length === 0) return null;

array is empty

heap is empty, extractMax returns null immediately

DSA Typescript

if (this.heap.length === 0) return null;

array has duplicates

duplicates are handled normally, kth largest is correct

DSA Typescript

no special guard needed, heap property handles duplicates

When to Use This Pattern

When asked to find the kth largest element efficiently, think of using a max heap to repeatedly extract the largest elements.

Common Mistakes

Mistake: Not rebuilding the heap after extracting max, causing incorrect heap structure
Fix: Call heapify(0) after replacing root with last element to maintain max heap

Mistake: Extracting max fewer or more than k times
Fix: Use a loop to extract max exactly k times

Summary

Finds the kth largest element by building a max heap and extracting the max k times.

Use when you want the kth largest without sorting the entire array.

The largest element is always at the root of the max heap, so repeated extraction gives kth largest.

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