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?"