Find Median from Data Stream — The Two-Heap Split Pattern

Problem Statement#

Design a data structure that supports adding integers from a stream and returning the median in O(log n) and O(1) time respectively.

Constraints:

• -10^5 <= num <= 10^5
• At least one element exists before calling findMedian
• At most 5 * 10^4 calls

addNum(1), addNum(2)   findMedian() = 1.5

addNum(1), addNum(2), addNum(3)   findMedian() = 2

Why This Problem Matters#

This is the canonical priority queue interview problem. Google, Meta, Amazon, and Bloomberg ask it almost weekly because it tests three skills at once: heap mechanics, invariant maintenance, and API design. Anyone serious about heap FAANG interviews must own this pattern cold.

Sorting per query is O(n log n). A balanced BST works but is overkill. The elegance of the two-heap split is that it uses only standard library primitives and runs in O(log n) per insert with O(1) median lookup.

The pattern generalizes to sliding-window median, kth element in a stream, and online quantile estimation, so it pays back many times over.

The Core Insight#

Split the stream into two halves. The lower half lives in a max-heap (so its top is the largest of the small numbers). The upper half lives in a min-heap (so its top is the smallest of the large numbers).

Keep sizes balanced within 1. The median is either the top of the larger heap, or the average of the two tops if they are equal.

Visual Dry Run#

Solution (Optimal)#

import heapq
 
class MedianFinder:
    def __init__(self):
        self.low = []   # max-heap (negated)
        self.high = []  # min-heap
 
    def addNum(self, num: int) -> None:
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
 
    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2.0

class MedianFinder {
    constructor() {
        this.low = new MaxHeap();
        this.high = new MinHeap();
    }
    addNum(num) {
        this.low.push(num);
        this.high.push(this.low.pop());
        if (this.high.size() > this.low.size()) {
            this.low.push(this.high.pop());
        }
    }
    findMedian() {
        if (this.low.size() > this.high.size()) return this.low.top();
        return (this.low.top() + this.high.top()) / 2;
    }
}

Time: addNum O(log n), findMedian O(1) — heap push/pop are logarithmic; tops are constant time. Space: O(n) — every stream element is stored once across the two heaps.

Common Mistakes#

• Pushing directly into the correct heap without the cross-balance step, breaking the ordering invariant
• Forgetting Python heapq is min-only and skipping the negation trick for the low heap
• Returning integer division when n is even, losing the .5
• Allowing size imbalance greater than 1
• Storing the entire stream in a list as a fallback, defeating the heap's purpose

Interview Tips#

• State the invariant first: every element in low is less than or equal to every element in high
• Draw the two heaps on the whiteboard before coding
• Always push to low first, pop the top, then push to high — the symmetry is easier to reason about than conditional branches
• Mention follow-ups proactively: integer-only buckets, sliding window, removing arbitrary elements

Follow-up Questions#

• What if 99% of values are between 0 and 100? Use a counting array for O(1) updates
• What if elements can be removed? Use a hash-map "lazy deletion" pattern on top of the heaps
• Sliding window median? See LeetCode 480 — same heaps plus a delayed-removal map
• What if values are doubles, not integers? Same algorithm, no change
• How do you handle thread safety in production? Wrap in a lock or use a concurrent skip list

Key Takeaways#

• Two-heap split is the gold standard for streaming median problems
• Max-heap for the lower half, min-heap for the upper half, keep sizes within 1
• Cross-balance trick (push-to-A, pop-A, push-to-B) makes the code symmetric
• O(log n) insert, O(1) query, O(n) space
• Python heapq is min-only — negate values for max-heap behavior
• This pattern generalizes to sliding-window median and online quantiles
• Memorize this as a heap FAANG interview must-know template