Kth Smallest Element Using Min Heap in DSA Typescript - Time & Space Complexity

Time Complexity: Kth Smallest Element Using Min Heap

O(n log n + k log n)

Understanding Time Complexity

We want to understand how the time needed to find the kth smallest element using a min heap changes as the input size grows.

Specifically, how does the number of steps grow when we add more numbers or change k?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function kthSmallest(arr: number[], k: number): number {
  const minHeap = new MinHeap();
  for (const num of arr) {
    minHeap.insert(num);
  }
  let result = -1;
  for (let i = 0; i < k; i++) {
    result = minHeap.extractMin();
  }
  return result;
}
    

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

Identify Repeating Operations

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

How Execution Grows With Input

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

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

Pattern observation: The total steps grow roughly with n plus k, but each insertion and extraction takes a small extra time that grows with the heap size.

Final Time Complexity

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

This means the time grows mostly by inserting all n elements into the heap and then extracting k times, each operation taking time related to the heap size.

Common Mistake

[X] Wrong: "Building the heap is just O(n) so the whole process is O(n + k)."

[OK] Correct: While heap construction can be done in O(n), each insertion here is done one by one, costing O(log n) each, so total insertion is O(n log n). Also, each extraction costs O(log n), so k extractions add up.

Interview Connect

Understanding this time complexity helps you explain why heaps are useful for selection problems and shows your grasp of how data structures affect performance.

Self-Check

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