ā† Back to DevBytes
JavaScript August 05, 2026 10 min read

Solving Find Median from Data Stream in JavaScript: Step-by-Step Guide

Introduction to Find Median from Data Stream

The "Find Median from Data Stream" problem is one of the most classic algorithmic challenges you will encounter in coding interviews and real-world data processing scenarios. The task is deceptively simple: design a data structure that supports adding numbers from a continuous stream and efficiently returning the median of all numbers seen so far at any point.

While computing the median of a static array is trivial ā€” sort the array and pick the middle element ā€” doing so repeatedly as new numbers arrive requires a more sophisticated approach. Naively re-sorting the entire collection on every insertion would result in O(n log n) time per operation, which becomes prohibitively expensive as the stream grows. In this tutorial, we will explore an optimal solution using two heaps, achieving O(log n) insertion and O(1) median retrieval.

What Is the Median?

The median of a set of numbers is the middle value when the numbers are arranged in sorted order. If the count of numbers is odd, the median is the single middle element. If the count is even, the median is typically defined as the average of the two middle elements.

For example, given the stream [5, 15, 1, 3], the sorted order is [1, 3, 5, 15]. Since there are four elements, the median is (3 + 5) / 2 = 4. If we then add 8, the sorted order becomes [1, 3, 5, 8, 15], and the median is 5.

Why This Problem Matters

Streaming median computation appears in many practical domains:

Unlike the mean, the median is resistant to extreme values, making it invaluable in skewed distributions. However, computing it efficiently in a streaming context is what makes this problem genuinely interesting.

The Naive Approach and Its Limitations

Before jumping to the optimal solution, let us understand why the straightforward approach falls short. The naive method stores all numbers in an array, sorts it whenever the median is requested, and returns the middle element(s).

class NaiveMedianFinder {
  constructor() {
    this.data = [];
  }

  addNum(num) {
    this.data.push(num);
  }

  findMedian() {
    this.data.sort((a, b) => a - b);
    const n = this.data.length;
    const mid = Math.floor(n / 2);
    if (n % 2 === 0) {
      return (this.data[mid - 1] + this.data[mid]) / 2;
    }
    return this.data[mid];
  }
}

This works correctly but is inefficient. Each call to findMedian triggers a full sort costing O(n log n) time. If you interleave n insertions with n median queries, the total cost balloons to O(nĀ² log n). For large streams, this is unacceptable.

The Optimal Approach: Two Heaps

The key insight is to maintain two heaps that partition the stream into two halves:

By keeping these two heaps balanced ā€” their sizes differ by at most one ā€” the median is always accessible from the heap tops in O(1) time. Insertions require O(log n) time to maintain the heap property.

How the Balancing Works

When a new number arrives, we decide which heap it belongs to and then rebalance if necessary:

This guarantees that the max-heap always contains the lower half and the min-heap always contains the upper half, with their tops giving us immediate access to the middle elements.

Computing the Median

Once the heaps are balanced:

Implementing a Heap in JavaScript

JavaScript does not provide a built-in priority queue or heap, so we need to implement one. Below is a generic binary heap implementation that supports both min-heap and max-heap behavior through a comparator function.

class Heap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  push(value) {
    this.data.push(value);
    this._siftUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this._siftDown(0);
    }
    return top;
  }

  _siftUp(index) {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      if (this.compare(this.data[index], this.data[parent]) < 0) {
        [this.data[index], this.data[parent]] = [this.data[parent], this.data[index]];
        index = parent;
      } else {
        break;
      }
    }
  }

  _siftDown(index) {
    const n = this.data.length;
    while (true) {
      let smallest = index;
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      if (left < n && this.compare(this.data[left], this.data[smallest]) < 0) {
        smallest = left;
      }
      if (right < n && this.compare(this.data[right], this.data[smallest]) < 0) {
        smallest = right;
      }

      if (smallest !== index) {
        [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
        index = smallest;
      } else {
        break;
      }
    }
  }
}

The compare function follows the same convention as Array.prototype.sort: it returns a negative number if the first argument should be higher in the heap. For a min-heap, we use (a, b) => a - b. For a max-heap, we reverse it with (a, b) => b - a.

Building the MedianFinder

With our heap implementation ready, we can now build the MedianFinder class that uses two heaps to track the median efficiently.

class MedianFinder {
  constructor() {
    // Max-heap for the lower half
    this.maxHeap = new Heap((a, b) => b - a);
    // Min-heap for the upper half
    this.minHeap = new Heap((a, b) => a - b);
  }

  addNum(num) {
    // Decide which heap to insert into
    if (this.maxHeap.size() === 0 || num <= this.maxHeap.peek()) {
      this.maxHeap.push(num);
    } else {
      this.minHeap.push(num);
    }

    // Rebalance the heaps
    if (this.maxHeap.size() > this.minHeap.size() + 1) {
      this.minHeap.push(this.maxHeap.pop());
    } else if (this.minHeap.size() > this.maxHeap.size()) {
      this.maxHeap.push(this.minHeap.pop());
    }
  }

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

Notice the rebalancing logic. We allow the max-heap to hold at most one extra element compared to the min-heap. This design choice means that when the total count is odd, the max-heap's top is always the median, simplifying the findMedian logic. If we instead allowed the min-heap to hold the extra element, we would just need to adjust the condition accordingly.

Testing the Implementation

Let us verify the implementation with a practical example that mirrors the scenario described earlier.

const finder = new MedianFinder();

finder.addNum(5);
console.log(finder.findMedian()); // 5

finder.addNum(15);
console.log(finder.findMedian()); // 10  (5 + 15) / 2

finder.addNum(1);
console.log(finder.findMedian()); // 5

finder.addNum(3);
console.log(finder.findMedian()); // 4  (3 + 5) / 2

finder.addNum(8);
console.log(finder.findMedian()); // 5

Let us trace through what happens internally. After adding 5, the max-heap contains [5] and the min-heap is empty, so the median is 5. After adding 15, it goes to the min-heap since 15 > 5, giving us max-heap [5] and min-heap [15], so the median is (5 + 15) / 2 = 10. Adding 1 places it in the max-heap, which now has two elements versus one in the min-heap, so we rebalance by moving 5 to the min-heap. The heaps become max-heap [1] and min-heap [5, 15], and the median is 5. The pattern continues correctly through the remaining insertions.

Complexity Analysis

Understanding the time and space complexity of this solution is essential for evaluating its suitability in production systems.

Compared to the naive approach, which costs O(n log n) per median query, the two-heap solution is dramatically faster for interleaved add-and-query workloads. For a stream of n elements with n median queries, the total cost drops from O(nĀ² log n) to O(n log n).

Handling Edge Cases

A robust implementation must account for several edge cases that can arise in real usage:

Here is an enhanced version with an explicit guard for the empty case:

findMedian() {
  if (this.maxHeap.size() === 0) {
    throw new Error("No numbers have been added yet.");
  }
  if (this.maxHeap.size() > this.minHeap.size()) {
    return this.maxHeap.peek();
  }
  return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
}

Best Practices

When implementing or using a streaming median finder in production, keep these best practices in mind:

Variation: Sliding Window Median

A common variation asks for the median over a sliding window of the last k elements. This is significantly harder because it requires both insertion and deletion of arbitrary elements. The two-heap approach alone does not support efficient arbitrary deletion. Solutions typically involve using two heaps augmented with lazy deletion and a hash map to track invalid entries, or using an ordered balanced binary search tree if the language provides one. While beyond the scope of this tutorial, understanding the basic two-heap technique is a prerequisite for tackling the sliding window variant.

Conclusion

The Find Median from Data Stream problem is a beautiful demonstration of how choosing the right data structure transforms an apparently expensive operation into an efficient one. By maintaining two heaps ā€” a max-heap for the lower half and a min-heap for the upper half ā€” we achieve O(log n) insertions and O(1) median queries, making the solution suitable for high-throughput streaming applications. The technique is not only a favorite in coding interviews but also a practical tool for real-time analytics, monitoring systems, and any domain where a robust measure of central tendency must be tracked continuously. Master this pattern, and you will have a powerful building block for a wide range of streaming data problems.

ā€” Ad ā€”

Google AdSense will appear here after approval

ā† Back to all articles