Kth Largest Element Using Max Heap in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert an element into the max heap.

DSA Typescript

function insert(heap: number[], value: number) {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0 && heap[index] [1] heap[Math.floor((index - 1) / 2)]) {
    [heap[index], heap[Math.floor((index - 1) / 2)]] = [heap[Math.floor((index - 1) / 2)], heap[index]];
    index = Math.floor((index - 1) / 2);
  }
}

Drag options to blanks, or click blank then click option'

A<=

B===

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causes min heap behavior.

Not swapping when child is greater breaks heap property.

We swap the current element with its parent if it is greater, to maintain max heap property.

2fill in blank

medium

Complete the code to heapify down after removing the max element.

DSA Typescript

function heapifyDown(heap: number[], index: number) {
  const length = heap.length;
  let largest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  if (left < length && heap[left] [1] heap[largest]) {
    largest = left;
  }
  if (right < length && heap[right] [1] heap[largest]) {
    largest = right;
  }
  if (largest !== index) {
    [heap[index], heap[largest]] = [heap[largest], heap[index]];
    heapifyDown(heap, largest);
  }
}

Drag options to blanks, or click blank then click option'

A>

B<

C===

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' causes incorrect heap structure.

Not checking both children leads to partial heap.

We compare children with the current largest to find the max child to swap with.

3fill in blank

hard

Fix the error in the code to extract the max element from the heap.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Aheap.length

B0

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using heap.length causes out-of-bound errors.

Using 1 or -1 skips the root and breaks heap property.

Heapify down starts from the root at index 0 after replacing it with the last element.

4fill in blank

hard

Fill both blanks to complete the function that finds the kth largest element using a max heap.

DSA Typescript

function findKthLargest(nums: number[], k: number): number {
  const heap: number[] = [];
  for (const num of nums) {
    insert(heap, num);
  }
  let result = 0;
  for (let i = 0; i < k; i++) {
    result = [1](heap);
  }
  return result;
}

Drag options to blanks, or click blank then click option'

AextractMax

BheapifyUp

CheapifyDown

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert instead of extractMax does not remove elements.

Using heapifyDown or heapifyUp directly is incorrect here.

We extract the max element k times to get the kth largest element.

5fill in blank

hard

Fill all three blanks to build a max heap from an array efficiently.

DSA Typescript

function buildMaxHeap(nums: number[]): number[] {
  const heap = [...nums];
  const start = Math.floor([1] / 2) - 1;
  for (let i = start; i >= 0; i--) {
    [2](heap, i);
  }
  return heap;
}

Drag options to blanks, or click blank then click option'

Aheap.length

BheapifyDown

Cnums.length

DheapifyUp

Attempts:

3 left

💡 Hint

Common Mistakes

Using heap.length before copying causes errors.

Using heapifyUp instead of heapifyDown breaks heap property.

We start heapifying down from the last parent node (length/2 -1) to build the heap.

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