Kth Largest Element Using Max Heap in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a max heap?

A max heap is a special tree-based data structure where the parent node is always greater than or equal to its child nodes. This means the largest element is always at the root.

beginner

How does a max heap help find the kth largest element?

By building a max heap from the array, the largest element is at the root. Removing the root k-1 times and then looking at the root gives the kth largest element.

intermediate

What is the time complexity of building a max heap from an array of size n?

Building a max heap takes O(n) time because heapify operations are done bottom-up efficiently.

intermediate

What is the time complexity of extracting the max element from a max heap?

Extracting the max element takes O(log n) time because after removing the root, heapify is done to restore the heap property.

beginner

Explain the steps to find the kth largest element using a max heap.

1. Build a max heap from the array.
2. Extract the max element (root) k-1 times.
3. The root now is the kth largest element.
4. Return this element.

What property does a max heap maintain?

A Nodes are sorted in ascending order

B Parent node is less than or equal to child nodes

C All nodes have equal values

D Parent node is greater than or equal to child nodes

A max heap always keeps the parent node greater than or equal to its children.

What is the root of a max heap?

A The smallest element

B The largest element

C The median element

D A random element

The root of a max heap is always the largest element.

How many times do you extract the max element to find the 3rd largest element?

A 3 times

B 1 time

C 2 times

D 4 times

You extract the max element k-1 times, so for the 3rd largest, extract 2 times.

What is the time complexity of extracting the max element from a max heap of size n?

A O(log n)

B O(1)

C O(n)

D O(n log n)

Extracting the max element requires heapify which takes O(log n) time.

Which of these is NOT a step to find the kth largest element using a max heap?

A Sort the array in ascending order

B Extract the max element k-1 times

C Build a max heap from the array

D Return the root of the heap

Sorting the array is not required when using a max heap to find the kth largest element.

Describe how to find the kth largest element using a max heap.

Think about the heap property and repeated extraction.

Explain why a max heap is useful for finding the kth largest element instead of sorting the whole array.

Consider efficiency and partial ordering.

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