Kth Largest Element Using Max Heap in DSA Javascript - Time & Space Complexity

Time Complexity: Kth Largest Element Using Max Heap

O(n log n + k log n)

Understanding Time Complexity

We want to understand how long it takes to find the kth largest number using a max heap.

How does the time needed grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findKthLargest(nums, k) {
  const maxHeap = new MaxHeap();
  for (const num of nums) {
    maxHeap.insert(num);
  }
  let result;
  for (let i = 0; i < k; i++) {
    result = maxHeap.extractMax();
  }
  return result;
}
    

This code builds a max heap from the array, then extracts the largest element k times to find the kth largest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting all n elements into the max heap and extracting the max k times.
• How many times: Insert runs n times; extractMax runs k times.

How Execution Grows With Input

As the input size n grows, building the heap takes more time, and extracting k times adds more steps.

Input Size (n)	Approx. Operations
10	About 10 insertions + k extractions
100	About 100 insertions + k extractions
1000	About 1000 insertions + k extractions

Insertion cost grows roughly with n log n, extraction cost grows with k log n, so total grows with both n and k.

Final Time Complexity

Time Complexity: O(n log n + k log n)

This means the time grows mostly by inserting all elements and then extracting k times, each step taking logarithmic time.

Common Mistake

[X] Wrong: "Building the heap is just O(n), so total time is O(n + k)."

[OK] Correct: Building a heap by inserting elements one by one costs O(n log n), not O(n), because each insert takes log n time. So total time is higher.

Interview Connect

Understanding this time complexity helps you explain why heap-based solutions are efficient and when they are better than sorting the whole list.

Self-Check

"What if we used a min heap of size k instead of a max heap of size n? How would the time complexity change?"

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Build a max heap from the array and extract the max element k times

B. Sort the array and pick the kth element from the start

C. Use a min heap to store all elements and pop k times

D. Reverse the array and pick the kth element

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 largest element.

2. Step 2: Extract max k times to get the kth largest

   By removing the root k times, the last extracted element is the kth largest.

3. Final Answer:

   Build max heap and extract max k times -> Option A

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to find kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Extracting fewer or more than k times

2. Which of the following is the correct way to create a max heap from an array arr in JavaScript using a custom heap class?

easy

A. const maxHeap = new MaxHeap(arr); maxHeap.heapify();

B. const maxHeap = new MaxHeap(); maxHeap.insert(arr);

C. const maxHeap = new MaxHeap(); maxHeap.build(arr);

D. const maxHeap = new MaxHeap(arr); maxHeap.buildHeap();

Solution

1. Step 1: Recognize typical max heap initialization

   Usually, a max heap class accepts an array and has a method like buildHeap() to create the heap structure.

2. Step 2: Identify correct method call

   buildHeap() is the standard method to convert the array into a max heap, so calling it after initialization is correct.

3. Final Answer:

   const maxHeap = new MaxHeap(arr); maxHeap.buildHeap(); -> Option D

4. Quick Check:

   buildHeap() builds max heap from array [OK]

Hint: Use buildHeap() after passing array to MaxHeap constructor [OK]

Common Mistakes:

• Calling insert with whole array instead of single elements
• Using wrong method names like heapify or build
• Not calling any method to build the heap

3. What will be the output of the following code snippet?

class MaxHeap {
  constructor(arr) {
    this.heap = arr;
    this.buildHeap();
  }
  buildHeap() {
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapify(i);
    }
  }
  heapify(i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
    if (right < this.heap.length && 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() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapify(0);
    return max;
  }
}

const arr = [3, 2, 1, 5, 6, 4];
const maxHeap = new MaxHeap(arr);
let kthLargest;
for (let i = 0; i < 2; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

medium

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Build max heap from array

   Array [3,2,1,5,6,4] becomes max heap with root 6 after buildHeap.

2. Step 2: Extract max twice

   First extractMax returns 6, second extractMax returns 5, so kthLargest after loop is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   2nd largest element = 5 [OK]

Hint: Extract max twice from max heap to get 2nd largest [OK]

Common Mistakes:

• Assuming heap root changes incorrectly after extraction
• Confusing 1st largest with 2nd largest
• Not updating heap after extraction

4. Identify the bug in the following code that tries to find the 3rd largest element using a max heap:

class MaxHeap {
  constructor(arr) {
    this.heap = arr;
    this.buildHeap();
  }
  buildHeap() {
    for (let i = 0; i < this.heap.length / 2; i++) {
      this.heapify(i);
    }
  }
  heapify(i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
    if (right < this.heap.length && 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() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapify(0);
    return max;
  }
}

const arr = [7, 10, 4, 3, 20, 15];
const maxHeap = new MaxHeap(arr);
let kthLargest;
for (let i = 0; i < 3; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

medium

A. The buildHeap loop should run backwards from middle to 0

B. extractMax should not call heapify after popping

C. heapify should swap with smallest child instead of largest

D. The array should be sorted before building the heap

Solution

1. Step 1: Analyze buildHeap loop direction

   Heap building requires heapify calls from last parent to root, so loop must run backwards from middle to 0.

2. Step 2: Identify incorrect loop direction

   Current loop runs forwards, which does not correctly heapify the tree, causing incorrect heap structure.

3. Final Answer:

   The buildHeap loop should run backwards from middle to 0 -> Option A

4. Quick Check:

   buildHeap loop direction = backwards [OK]

Hint: buildHeap loop must run backwards from middle to root [OK]

Common Mistakes:

• Running buildHeap loop forwards
• Not calling heapify after extractMax
• Swapping with wrong child in heapify

5. Given an array arr = [12, 3, 5, 7, 19, 0, 4], write a JavaScript function using a max heap to find the 4th largest element. What is the output of your function?

hard

A. 4

B. 5

C. 7

D. 3

Solution

1. Step 1: Build max heap from array

   Array becomes max heap with root 19 after heapify.

2. Step 2: Extract max 4 times

   Extracted elements in order: 19, 12, 7, 5. The 4th largest is 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   4th largest element = 7 [OK]

Hint: Extract max k times; last extracted is kth largest [OK]

Common Mistakes:

• Extracting fewer times than k
• Confusing 3rd largest with 4th largest
• Not rebuilding heap after extraction