← Back to DevBytes
Developer Tutorial July 09, 2026 14 min read

Find Median from Data Stream: Multiple Solutions and Complexity Analysis

Find Median from Data Stream: Multiple Solutions and Complexity Analysis

The Find Median from Data Stream problem is a classic algorithm design challenge that tests your ability to handle real-time, unbounded data efficiently. In this tutorial, we'll explore every viable solution — from the naive approach to the industry-standard two-heap technique — with complete code, complexity breakdowns, and practical guidance for choosing the right approach in production.

1. Understanding the Problem

What is a data stream? Unlike a static array, a data stream delivers numbers one at a time, and you don't know the total count in advance. You must support two operations interleaved arbitrarily:

What is the median? The median is the "middle" value in an ordered sequence. If the count of numbers is odd, it's the exact middle element. If the count is even, it's the arithmetic mean of the two middle elements.

For example, given the stream: [5, 15, 1, 3] ingested in that order:

Why this problem matters. It appears in real-time analytics dashboards, financial tickers, sensor monitoring systems, and anywhere you need percentile metrics without storing the full history. Tech companies (Google, Meta, Amazon) use it as an interview staple because it reveals how you think about data structures under constraints.

2. Solution 1: Naive Sorting on Each Query

The simplest mental model: keep an unsorted list. When findMedian() is called, sort the list and compute the median.

class MedianFinderNaive:
    def __init__(self):
        self.data = []

    def addNum(self, num: int) -> None:
        self.data.append(num)

    def findMedian(self) -> float:
        self.data.sort()
        n = len(self.data)
        if n % 2 == 1:
            return float(self.data[n // 2])
        else:
            mid = n // 2
            return (self.data[mid - 1] + self.data[mid]) / 2.0

Complexity:

Verdict: This is unacceptable for production. If you have 1 million elements and call findMedian() 100 times per second, you're doing 100 full sorts per second on a growing array. The latency becomes unusable quickly.

3. Solution 2: Maintain a Sorted List via Bisect / Insertion Sort

Instead of sorting from scratch each time, keep the list sorted by inserting each new element into its correct position. Python's bisect.insort makes this trivial.

import bisect

class MedianFinderSortedInsert:
    def __init__(self):
        self.data = []

    def addNum(self, num: int) -> None:
        bisect.insort_left(self.data, num)

    def findMedian(self) -> float:
        n = len(self.data)
        if n % 2 == 1:
            return float(self.data[n // 2])
        else:
            mid = n // 2
            return (self.data[mid - 1] + self.data[mid]) / 2.0

Complexity:

Verdict: This inverts the cost. findMedian is now lightning-fast, but addNum becomes O(n). For high-ingest-rate streams (e.g., 10,000 adds per second), the linear insertion cost is prohibitive. This is only viable when adds are rare and median queries are frequent.

4. Solution 3: Two Heaps — The Optimal Approach

This is the canonical solution that balances both operations beautifully. The insight: you don't need the entire array sorted. You only need access to the middle element(s). By splitting the stream into two halves — a max-heap for the lower half and a min-heap for the upper half — you can maintain the median in O(log n) per operation.

Core invariants:

Median computation:

Here is the complete, production-quality implementation in Python:

import heapq

class MedianFinderTwoHeaps:
    def __init__(self):
        # max-heap for the lower half (invert values to use Python's min-heap as max-heap)
        self.lower = []  # stores negative values to simulate max-heap behavior
        # min-heap for the upper half
        self.upper = []

    def addNum(self, num: int) -> None:
        # Step 1: Push to the appropriate heap
        # Always push to lower first (with negation for max-heap), then rebalance
        heapq.heappush(self.lower, -num)

        # Step 2: Ensure every element in lower is <= every element in upper
        # Move the largest from lower to upper
        if self.lower and self.upper:
            if -self.lower[0] > self.upper[0]:
                val = -heapq.heappop(self.lower)
                heapq.heappush(self.upper, val)

        # Step 3: Balance sizes: lower can have at most 1 more element than upper
        if len(self.lower) > len(self.upper) + 1:
            val = -heapq.heappop(self.lower)
            heapq.heappush(self.upper, val)
        elif len(self.upper) > len(self.lower):
            val = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -val)

    def findMedian(self) -> float:
        if len(self.lower) > len(self.upper):
            # Odd count: median is top of lower (remember to negate back)
            return float(-self.lower[0])
        elif len(self.lower) == len(self.upper):
            # Even count: average of both tops
            return (-self.lower[0] + self.upper[0]) / 2.0
        else:
            # This case shouldn't occur if balancing is correct, but handle gracefully
            return float(-self.lower[0])

Let's trace the example stream [5, 15, 1, 3] step by step to solidify understanding:

# Initial state: lower=[], upper=[]

# addNum(5)
# Push -5 to lower: lower=[-5], upper=[]
# Sizes: lower=1, upper=0 → balanced (odd count). Median = 5.

# addNum(15)
# Push -15 to lower: lower=[-15, -5] (heap order: -15 is top since -15 < -5)
# Check: top of lower = -(-15) = 15, upper is empty → no cross-check needed yet
# But lower size (2) > upper size (0) + 1 → rebalance: pop -15 from lower, push 15 to upper
# lower=[-5], upper=[15]
# Sizes: lower=1, upper=1 → even count. Median = (5+15)/2 = 10.

# addNum(1)
# Push -1 to lower: lower=[-5, -1] (top is -5 → value 5)
# Check: -lower[0]=5 > upper[0]=15? No (5 < 15), so no swap needed
# Sizes: lower=2, upper=1 → lower > upper+1? No (2 == 1+1, which is allowed for odd count)
# Median = top of lower = 5. Correct!

# addNum(3)
# Push -3 to lower: lower=[-5, -1, -3] (top is -5 → value 5)
# Check: -lower[0]=5 > upper[0]=15? No. No swap.
# Sizes: lower=3, upper=1 → lower > upper+1? Yes (3 > 2) → rebalance
# Pop -5 from lower (value 5), push 5 to upper: upper=[5, 15], lower=[-3, -1] (top -3→3, then -1→1)
# Sizes: lower=2, upper=2 → even. Median = (3+5)/2 = 4. Correct!

Complexity:

Verdict: This is the gold standard. It handles millions of elements effortlessly, with balanced performance for both operations. It's the solution you should default to in interviews and production.

5. Solution 4: Balanced Binary Search Tree (BST)

If you have access to a self-balancing BST that supports order statistics (like finding the k-th smallest element in O(log n)), you can use it directly. In Python, you'd need a library like sortedcontainers or implement a custom AVL/Red-Black tree. In Java, TreeMap or Guava's TreeMultiset can serve.

Here's a Python example using the sortedcontainers library (not in the standard library, but excellent for production):

from sortedcontainers import SortedList

class MedianFinderBST:
    def __init__(self):
        self.data = SortedList()

    def addNum(self, num: int) -> None:
        self.data.add(num)  # O(log n) insertion

    def findMedian(self) -> float:
        n = len(self.data)
        if n % 2 == 1:
            return float(self.data[n // 2])
        else:
            mid = n // 2
            return (self.data[mid - 1] + self.data[mid]) / 2.0

Complexity:

Verdict: Elegant but often overkill. The two-heap solution is simpler to implement from scratch and doesn't require external libraries. However, if you need percentile queries beyond just the median (e.g., arbitrary percentiles), a BST with order statistics becomes more versatile.

6. Solution 5: Counting / Bucketing for Constrained Integer Streams

In specialized scenarios where all numbers are integers within a known, bounded range (e.g., ages 0–120, or sensor readings 0–1023), you can use a counting array or bucket-based approach for O(1) operations.

class MedianFinderCounting:
    def __init__(self, min_val: int, max_val: int):
        self.min_val = min_val
        self.max_val = max_val
        self.range_size = max_val - min_val + 1
        self.counts = [0] * self.range_size
        self.total_count = 0

    def addNum(self, num: int) -> None:
        if self.min_val <= num <= self.max_val:
            self.counts[num - self.min_val] += 1
            self.total_count += 1
        else:
            raise ValueError(f"Number {num} out of range [{self.min_val}, {self.max_val}]")

    def findMedian(self) -> float:
        if self.total_count == 0:
            return 0.0
        
        target = self.total_count // 2
        cumulative = 0
        median1 = None
        median2 = None
        
        for i, count in enumerate(self.counts):
            cumulative += count
            if cumulative > target:
                if median1 is None:
                    median1 = i + self.min_val
                if median2 is None and self.total_count % 2 == 0 and cumulative - count <= target - 1:
                    # Need two middle elements for even count
                    if cumulative - count == target:
                        median1 = i + self.min_val
                    else:
                        median1 = i + self.min_val
                break
            elif cumulative == target:
                if self.total_count % 2 == 1:
                    # Odd count: find next non-zero
                    for j in range(i + 1, self.range_size):
                        if self.counts[j] > 0:
                            return float(j + self.min_val)
                else:
                    median1 = i + self.min_val
                    # Find next non-zero for median2
                    for j in range(i + 1, self.range_size):
                        if self.counts[j] > 0:
                            median2 = j + self.min_val
                            return (median1 + median2) / 2.0
                    return float(median1)  # fallback
        
        return float(median1 if median1 is not None else 0)

For a cleaner implementation when the range is small, you can also maintain a running cumulative count and simply walk the buckets:

class MedianFinderBuckets:
    def __init__(self, min_val: int, max_val: int):
        self.min_val = min_val
        self.buckets = [0] * (max_val - min_val + 1)
        self.n = 0

    def addNum(self, num: int) -> None:
        self.buckets[num - self.min_val] += 1
        self.n += 1

    def findMedian(self) -> float:
        half = self.n // 2
        count = 0
        for i, freq in enumerate(self.buckets):
            count += freq
            if count > half:
                if self.n % 2 == 1 or (self.n % 2 == 0 and count - freq <= half - 1):
                    return float(i + self.min_val)
                # Even case: need to find two middle values
                # First middle is at current index, find second
                if count - freq == half:
                    # The boundary falls exactly at the start of this bucket
                    # The first middle is this value, second middle is also this value if freq > 1
                    # or we need to find the next value
                    return float(i + self.min_val) if freq > 1 else self._find_next(i)
                # Otherwise, the two medians straddle a boundary
                # This simplified version assumes dense ranges; 
                # for sparse ranges, a more precise walk is needed
                return float(i + self.min_val)
        return 0.0

    def _find_next(self, idx):
        for j in range(idx + 1, len(self.buckets)):
            if self.buckets[j] > 0:
                return float(j + self.min_val)
        return float(idx + self.min_val)

Complexity:

Verdict: Extremely fast for bounded integer ranges. Common in monitoring systems where metrics have known bounds. Not applicable for floating-point or unbounded integer streams.

7. Comprehensive Complexity Comparison

Here's a summary table to help you choose the right approach instantly:

┌─────────────────────────┬──────────────┬────────────────┬───────────┬──────────────┐
│       Approach          │  addNum      │  findMedian    │  Space    │  Notes        │
├─────────────────────────┼──────────────┼────────────────┼───────────┼──────────────┤
│ Naive sorting           │  O(1)        │  O(n log n)    │  O(n)     │  Too slow     │
│ Sorted insertion        │  O(n)        │  O(1)          │  O(n)     │  Good for rare│
│                         │              │                │           │  adds         │
│ Two Heaps (optimal)     │  O(log n)    │  O(1)          │  O(n)     │  Best general │
│ Balanced BST            │  O(log n)    │  O(log n)/O(1) │  O(n)     │  Versatile    │
│ Counting/Buckets        │  O(1)        │  O(R)          │  O(R)     │  Only bounded │
│                         │              │                │           │  integers     │
└─────────────────────────┴──────────────┴────────────────┴───────────┴──────────────┘

8. Java Implementation of the Two-Heaps Approach

For Java developers, here's a complete implementation using PriorityQueue:

import java.util.PriorityQueue;
import java.util.Collections;

class MedianFinder {
    private PriorityQueue<Integer> lower; // max-heap for lower half
    private PriorityQueue<Integer> upper; // min-heap for upper half

    public MedianFinder() {
        // Use Collections.reverseOrder() to create a max-heap
        lower = new PriorityQueue<>(Collections.reverseOrder());
        upper = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // Always add to lower first
        lower.offer(num);

        // Ensure every element in lower <= every element in upper
        if (!lower.isEmpty() && !upper.isEmpty()) {
            if (lower.peek() > upper.peek()) {
                upper.offer(lower.poll());
            }
        }

        // Balance sizes: lower can have at most 1 more element than upper
        if (lower.size() > upper.size() + 1) {
            upper.offer(lower.poll());
        } else if (upper.size() > lower.size()) {
            lower.offer(upper.poll());
        }
    }

    public double findMedian() {
        if (lower.size() > upper.size()) {
            return (double) lower.peek();
        } else if (lower.size() == upper.size()) {
            return (lower.peek() + upper.peek()) / 2.0;
        }
        return 0.0; // fallback, shouldn't happen
    }
}

Usage example:

MedianFinder mf = new MedianFinder();
mf.addNum(5);
System.out.println(mf.findMedian()); // 5.0
mf.addNum(15);
System.out.println(mf.findMedian()); // 10.0
mf.addNum(1);
System.out.println(mf.findMedian()); // 5.0
mf.addNum(3);
System.out.println(mf.findMedian()); // 4.0

9. Edge Cases and Follow-Up Questions

Empty stream: What should findMedian() return when no numbers have been added? Options include returning None (Python), throwing an exception, returning 0.0, or returning Double.NaN. Document this clearly in your API contract.

Duplicate values: The two-heap approach handles duplicates naturally. Multiple identical values will be distributed across both heaps based on arrival order and rebalancing, which is correct — the median is unaffected.

Integer overflow: When averaging two integers for the even-count median, use (a + b) / 2.0 or (a / 2.0) + (b / 2.0) to avoid overflow in languages with fixed-size integers (Java, C++). Python's arbitrary-precision integers don't have this issue.

Common follow-up questions in interviews:

10. Best Practices for Production

11. Conclusion

The Find Median from Data Stream problem is a beautiful demonstration of how choosing the right data structure transforms performance. We've journeyed from the naive O(n log n) sorting approach through sorted insertion, counting buckets, and balanced BSTs, arriving at the elegant two-heap solution that delivers O(log n) inserts and O(1) median queries. This technique is not just interview trivia — it powers real-world systems in finance, IoT, and analytics where real-time percentile metrics are mission-critical.

The key insight to carry forward: you rarely need full sorted order. Often, maintaining just the boundary between two halves is enough. This principle of "partial order" applies far beyond median finding — to sliding window maxima, percentile approximations, and priority-based scheduling systems. Master the two-heap pattern, and you'll see its shape in problems across the entire algorithmic landscape.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles