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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of extracting the 3rd largest element using a max heap

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

DSA Typescript

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

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.sinkDown(0);
    return max;
  }

  sinkDown(index: number) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swapIdx: number | null = null;

      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx] > element) {
          swapIdx = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        if (
          (swapIdx === null && this.heap[rightChildIdx] > element) ||
          (swapIdx !== null && this.heap[rightChildIdx] > this.heap[leftChildIdx])
        ) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
      index = swapIdx;
    }
  }
}

const nums = [7, 10, 4, 3, 20, 15];
const k = 3;
const maxHeap = new MaxHeap();
for (const num of nums) {
  maxHeap.insert(num);
}
let kthLargest: number | undefined;
for (let i = 0; i < k; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

A 7

B 15

C 10

D 20

💡 Hint

Remember that the max heap always extracts the largest element first. Extract k times to get the kth largest.

The max heap inserts all numbers. Extracting max 3 times gives: 20 (1st), 15 (2nd), 10 (3rd). The last extracted value is 10, which is printed. Option C.

❓ Predict Output

intermediate

Output after building max heap and extracting max once

What is the state of the heap array after inserting [5, 3, 8, 4] and extracting the max once?

DSA Typescript

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

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.sinkDown(0);
    return max;
  }

  sinkDown(index: number) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swapIdx: number | null = null;

      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx] > element) {
          swapIdx = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        if (
          (swapIdx === null && this.heap[rightChildIdx] > element) ||
          (swapIdx !== null && this.heap[rightChildIdx] > this.heap[leftChildIdx])
        ) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
      index = swapIdx;
    }
  }
}

const maxHeap = new MaxHeap();
[5, 3, 8, 4].forEach(n => maxHeap.insert(n));
maxHeap.extractMax();
console.log(maxHeap.heap);

A [5, 4, 3]

B [8, 5, 3, 4]

C [5, 4, 3, 8]

D [4, 5, 3]

💡 Hint

After extracting max, the heap reorders to maintain max heap property.

Initial heap after inserts is [8, 4, 5, 3]. Extract max removes 8, replaces root with 3 (last), then sinks down: swaps with larger child 5 at index 2, resulting in [5, 4, 3].

🔧 Debug

advanced

Identify the error in max heap sinkDown method

What error will occur when running this sinkDown method in a max heap implementation?

DSA Typescript

sinkDown(index: number) {
  const length = this.heap.length;
  const element = this.heap[index];
  while (true) {
    let leftChildIdx = 2 * index + 1;
    let rightChildIdx = 2 * index + 2;
    let swapIdx: number | null = null;

    if (leftChildIdx < length) {
      if (this.heap[leftChildIdx] < element) {
        swapIdx = leftChildIdx;
      }
    }
    if (rightChildIdx < length) {
      if (
        (swapIdx === null && this.heap[rightChildIdx] < element) ||
        (swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])
      ) {
        swapIdx = rightChildIdx;
      }
    }
    if (swapIdx === null) break;
    [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
    index = swapIdx;
  }
}

A The sinkDown will incorrectly swap smaller children, breaking max heap property

B The code will cause an infinite loop because swapIdx is never updated

C The code will throw a TypeError due to undefined heap elements

D No error; the sinkDown method works correctly

💡 Hint

Check the comparison operators used for deciding swaps in a max heap.

The sinkDown method uses '<' comparisons, which is for min heap. For max heap, it should use '>' to swap with larger children. Using '<' causes the heap to swap with smaller children, breaking max heap property.

🚀 Application

advanced

Find the 2nd largest element using max heap

Given the array [12, 3, 5, 7, 19], what is the 2nd largest element found by extracting max twice from a max heap?

DSA Typescript

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

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.sinkDown(0);
    return max;
  }

  sinkDown(index: number) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swapIdx: number | null = null;

      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx] > element) {
          swapIdx = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        if (
          (swapIdx === null && this.heap[rightChildIdx] > element) ||
          (swapIdx !== null && this.heap[rightChildIdx] > this.heap[leftChildIdx])
        ) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
      index = swapIdx;
    }
  }
}

const nums = [12, 3, 5, 7, 19];
const maxHeap = new MaxHeap();
for (const num of nums) {
  maxHeap.insert(num);
}
maxHeap.extractMax();
const secondLargest = maxHeap.extractMax();
console.log(secondLargest);

A 19

B 12

C 7

D 5

💡 Hint

Extract max twice; the first extraction removes the largest, the second is the 2nd largest.

The largest element is 19, extracted first. The next largest is 12, extracted second. So output is 12.

🧠 Conceptual

expert

Time complexity of finding kth largest element using max heap

What is the time complexity of finding the kth largest element in an unsorted array of size n by building a max heap and extracting max k times?

A O(nk)

B O(n log n + k)

C O(k log n)

D O(n + k log n)

💡 Hint

Building a max heap from n elements takes O(n). Each extraction takes O(log n).

Building the max heap is O(n). Extracting max k times costs O(k log n). Total is O(n + k log n).

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