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

Time Complexity: Kth Largest Element Using Max Heap

O(n log n + k log n)

Understanding Time Complexity

We want to know how the time needed to find the kth largest element changes as the input size grows.

Specifically, how the operations scale when using a max heap to solve this problem.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Inserting each element into the max heap and extracting the max element k times.
• How many times: Insert runs n times (once per element), extractMax runs k times.

How Execution Grows With Input

As the input size n grows, building the heap requires more insertions, each taking some time. Extracting k times also takes time depending on k.

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

Pattern observation: Insertions grow linearly with n, extractions grow linearly with k, each operation takes time proportional to log n.

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 operation taking about log n steps.

Common Mistake

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

[OK] Correct: While heap construction can be done in O(n), inserting elements one by one as in this code costs O(n log n). So the total time is higher than just O(n).

Interview Connect

Understanding how heap operations add up helps you explain your solution clearly and shows you know how to analyze performance in real problems.

Self-Check

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