Find Median Data Stream LeetCode 295

LeetCode 295 asks you to design a data structure called MedianFinder that supports two operations: addNum(int num) which adds a number from the data stream to the structure, and findMedian() which returns the median of all numbers added so far. Numbers arrive one at a time — you never see the full dataset upfront.

The median is defined as the middle value in a sorted list. If the total count is odd, it is the single middle element. If even, it is the average of the two middle elements. For example, after adding [1, 2, 3] the median is 2; after adding [1, 2] the median is 1.5.

Key constraints to keep in mind: up to 50,000 calls to addNum and findMedian combined, values in range [-100,000, 100,000], and at least one element before findMedian is called. The follow-up challenge asks: can you optimize if all integers are in [0, 100], or if 99% fall in [0, 100]?

The most intuitive approach is to maintain a sorted array. On each addNum call, binary search to find the insertion point and insert. findMedian then reads the middle element directly. Binary search itself is O(log n), but insertion into a sorted array requires shifting elements — O(n) per addNum call.

A second naive approach defers sorting: just append to an unsorted array on addNum, then fully sort on findMedian. This makes addNum O(1) but findMedian O(n log n). If findMedian is called after every addNum, the total cost is still O(n^2 log n) across all operations.

Both approaches are too slow when n reaches 50,000 operations. What you need is a data structure that maintains order incrementally without paying the full sort cost each time.

The core idea is to split your numbers into two halves at all times. A max-heap holds the smaller half of the numbers, and a min-heap holds the larger half. The top of the max-heap is the largest number in the lower half; the top of the min-heap is the smallest number in the upper half.

To find the median: if the total count is odd, one heap has one extra element and its top is the median. If even, the median is the average of both tops. You never need to sort anything — the answer sits right at the heap tops.

The constraint is that the heaps must stay balanced: their sizes differ by at most one. Specifically, we maintain the invariant that the max-heap size is always greater than or equal to the min-heap size, and at most one larger. This lets us pick the right heap to read from for the median.

The balancing algorithm has two steps. First, always push the new number onto the max-heap, then immediately pop the max-heap top and push it to the min-heap. This ensures every number passes through the max-heap and any number larger than the current lower half migrates to the upper half.

Second, if the min-heap grows larger than the max-heap after the first step, pop the min-heap top and push it back to the max-heap. This restores the size invariant. After these at-most-two operations, the heaps are balanced again.

Why always push to max-heap first? It routes the new number through a comparison with the current median boundary. If the new number is smaller than the current median, it stays in the max-heap. If larger, it ends up in the min-heap. The rebalance step then corrects the size difference if needed.

If all integers are guaranteed to be in the range [0, 100], you can use a bucket counting array of size 101. Increment the bucket on addNum in O(1). For findMedian, scan through the buckets to find the middle count — at most 101 iterations, effectively O(1).

If 99% of integers fall in [0, 100] but outliers exist, use a hybrid: bucket counting for in-range values plus two small heaps for out-of-range outliers. Track the total count carefully so findMedian knows whether the median falls in the bucket range or in the outlier heaps.

These optimizations illustrate a broader principle: when input distribution is constrained, you can often beat the general-case complexity. The interviewer asking this follow-up is testing whether you can reason about tradeoffs between generality and performance.

In Python, heapq only provides a min-heap. To simulate a max-heap for the lower half, negate all values before pushing and negate again when popping. The max-heap stores negated values so the smallest negated value (most negative) corresponds to the largest actual value. The min-heap stores values as-is.

In Java, PriorityQueue defaults to a min-heap. Create the max-heap with Collections.reverseOrder() or a lambda comparator. The addNum logic is identical: offer to maxHeap, then poll from maxHeap and offer to minHeap, then rebalance if needed. findMedian reads maxHeap.peek() when sizes differ, or the average of both peeks.

Time complexity: addNum is O(log n) due to heap push and pop operations. findMedian is O(1) — just reading the top elements. Space complexity is O(n) for n numbers stored across both heaps. This is the optimal complexity class for the general streaming median problem.

Find Median from Data Stream is the gateway to harder heap problems. Sliding Window Median (LeetCode 480) extends the two-heap approach with lazy deletion to handle a moving window — you need to remove elements leaving the window without breaking the heap structure.

K Closest Points to Origin (LeetCode 973) and Top K Frequent Elements (LeetCode 347) use a fixed-size k heap to avoid sorting the entire collection. Merge K Sorted Lists (LeetCode 23) uses a min-heap to merge multiple sorted sequences in O(n log k) time.

The unifying theme across all heap pattern problems: heaps are excellent when you only care about the extreme elements (min or max) and need to maintain that property dynamically as elements are added or removed. Once you internalize the two-heap balancing trick from LeetCode 295, the rest of the heap family becomes much more approachable.