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

Time Complexity: Median of Data Stream Using Two Heaps

O(log n)

Understanding Time Complexity

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

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class MedianFinder {
  private maxHeap: number[] = [] // smaller half
  private minHeap: number[] = [] // larger half

  addNum(num: number): void {
    if (!this.maxHeap.length || num <= -this.maxHeap[0]) {
      this.maxHeapPush(-num)
    } else {
      this.minHeapPush(num)
    }
    this.balanceHeaps()
  }

  findMedian(): number {
    if (this.maxHeap.length > this.minHeap.length) {
      return -this.maxHeap[0]
    } else {
      return (-this.maxHeap[0] + this.minHeap[0]) / 2
    }
  }

  private maxHeapPush(val: number) { /* push and heapify */ }
  private minHeapPush(val: number) { /* push and heapify */ }
  private balanceHeaps() { /* move elements to keep sizes balanced */ }
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding a number involves inserting into a heap and balancing heaps.
• How many times: Each addNum call does these operations once per number added.

How Execution Grows With Input

Each new number causes a few heap operations that take time related to the heap size.

Input Size (n)	Approx. Operations
10	About 10 insertions and balancing steps, each small.
100	About 100 insertions, each a bit longer due to bigger heaps.
1000	About 1000 insertions, each slightly longer but still efficient.

Pattern observation: The time per insertion grows slowly as heaps grow, not linearly.

Final Time Complexity

Time Complexity: O(log n)

This means adding each number and updating the median takes time that grows slowly with the total numbers added.

Common Mistake

[X] Wrong: "Adding a number takes constant time because it's just one step."

[OK] Correct: Actually, adding to a heap requires rearranging elements to keep order, which takes time growing with heap size.

Interview Connect

Knowing how to keep track of medians efficiently shows you can handle data that changes over time, a useful skill in many real problems.

Self-Check

"What if we used a sorted array instead of heaps? How would the time complexity change?"