Kth Largest Element Using Max Heap in DSA Typescript - Execution Trace

Concept Flow - Kth Largest Element Using Max Heap

Build Max Heap from array

↓

Extract max element (root)

↓

Replace root with last element

↓

Heapify to restore max heap

↓

Repeat extraction k times

↓

Last extracted element is kth largest

Build a max heap from the array, then remove the largest element k times. The last removed element is the kth largest.

Execution Sample

DSA Typescript

function heapify(nums: number[], heapSize: number, i: number): void {
  let largest = i;
  const l = 2 * i + 1;
  const r = 2 * i + 2;
  if (l < heapSize && nums[l] > nums[largest]) largest = l;
  if (r < heapSize && nums[r] > nums[largest]) largest = r;
  if (largest !== i) {
    [nums[i], nums[largest]] = [nums[largest], nums[i]];
    heapify(nums, heapSize, largest);
  }
}

function findKthLargest(nums: number[], k: number): number {
  let heapSize = nums.length;
  for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
    heapify(nums, heapSize, i);
  }
  for (let i = 0; i < k; i++) {
    const max = nums[0];
    nums[0] = nums[heapSize - 1];
    heapSize--;
    heapify(nums, heapSize, 0);
    if (i === k - 1) return max;
  }
  return -1;
}

This code builds a max heap from the array (O(n)) and extracts the max element k times (O(k log n)) to find the kth largest.

Execution Table

Step	Operation	Nodes in Heap Array	Pointer Changes	Visual State (Heap Tree)
1	Build max heap from [3,2,1,5,6,4]	[6,5,4,3,2,1]	Heap built, root at index 0	6 / \ 5 4 / \ / 3 2 1
2	Extract max (6)	[5,3,4,1,2]	Root replaced by last element (1), heapify from root	5 / \ 3 4 / \ 1 2
3	Extract max (5)	[4,3,2,1]	Root replaced by last element (2), heapify from root	4 / \ 3 2 / 1
4	Extract max (4)	[3,1,2]	Root replaced by last element (1), heapify from root	3 / \ 1 2
5	Extract max (3)	[2,1]	Root replaced by last element (1), heapify from root	2 / 1
6	Extract max (2)	[1]	Root replaced by last element (1), heapify not needed	1
7	Extract max (1)	[]	Heap empty after extraction	(empty)

💡 Extraction stops after k times; last extracted element is kth largest.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
nums (heap array)	[3,2,1,5,6,4]	[5,3,4,1,2]	[4,3,2,1]	[3,1,2]	[2,1]	[1]	[]	[]
extracted max	N/A	6	5	4	3	2	1	N/A
k	3 (example)	3	3	3	3	3	3	3

Key Moments - 3 Insights

Why do we replace the root with the last element before heapifying?

Because the root (max element) is removed, we need to fill the root position to keep the heap complete. The last element moves to root, then heapify fixes the heap property (see execution_table step 2).

Why do we heapify only from the root after extraction?

Only the root may violate the max heap property after replacement. Heapify from root restores order efficiently (see execution_table steps 2-6).

How do we know when to stop extracting elements?

We extract exactly k times. The last extracted max is the kth largest element (see exit_note and variable_tracker extracted max after 3 extractions).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the root of the heap after extraction?

A 5

B 1

C 4

D 3

💡 Hint

Check the 'Visual State' column at step 3 in execution_table.

After the first extraction and heapify (step 2), what is the heap array?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Nodes in Heap Array' column in execution_table.

If k=4, what is the extracted max value after the last extraction?

A 4

B 3

C 5

D 6

💡 Hint

Check the 'extracted max' row in variable_tracker after 4 extractions.

Concept Snapshot

Kth Largest Element Using Max Heap:
- Build max heap from array
- Extract max element k times
- Each extraction: replace root with last element, then heapify
- Last extracted max is kth largest
- Efficient for large arrays, O(n + k log n) time

Full Transcript

To find the kth largest element using a max heap, first build a max heap from the input array. The max heap ensures the largest element is at the root. Then, extract the max element k times. Each extraction removes the root, replaces it with the last element in the heap, and heapifies from the root to restore the max heap property. After k extractions, the last extracted element is the kth largest. This method efficiently finds the kth largest without sorting the entire array.

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