Median of Data Stream Using Two Heaps in DSA Javascript - Time & Space Complexity

Time Complexity: Median of Data Stream Using Two Heaps

O(log n)

Understanding Time Complexity

We want to know how fast we can find the middle value when numbers keep coming in.

How does the time to add numbers and get the middle change as more numbers arrive?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class MedianFinder {
  constructor() {
    this.small = new MaxHeap(); // lower half
    this.large = new MinHeap(); // upper half
  }

  addNum(num) {
    this.small.insert(num);
    this.large.insert(this.small.extractMax());
    if (this.large.size() > this.small.size()) {
      this.small.insert(this.large.extractMin());
    }
  }

  findMedian() {
    if (this.small.size() > this.large.size()) return this.small.peek();
    return (this.small.peek() + this.large.peek()) / 2;
  }
}
    

This code keeps two heaps to quickly find the median as numbers are added.

Identify Repeating Operations

Look at what repeats when adding numbers.

• Primary operation: Inserting and extracting from heaps (insert, extractMax, extractMin).
• How many times: Each addNum call does a few heap operations, each on a smaller set of numbers.

How Execution Grows With Input

Each new number causes a few heap operations that take longer as the heaps grow.

Input Size (n)	Approx. Operations
10	About 10 insertions and extractions, each quick.
100	About 100 insertions and extractions, each a bit slower.
1000	About 1000 insertions and extractions, each slower but still efficient.

Pattern observation: The time per add grows slowly, roughly like the height of the heaps, which grows with the log of input size.

Final Time Complexity

Time Complexity: O(log n)

This means adding each number and updating the median takes time that grows slowly as more numbers come in.

Common Mistake

[X] Wrong: "Adding a number takes constant time because we just put it somewhere."

[OK] Correct: Actually, we must keep the heaps balanced and ordered, so inserting and extracting take time that grows with the heap size.

Interview Connect

Understanding this method shows you can handle data that changes over time and still find answers quickly.

Self-Check

"What if we used only one heap instead of two? How would the time complexity change?"