Find Median from Data Stream
Understanding the Problem
Finding a median in a static, sorted array is direct: take the middle element, or average the two middle elements when the length is even. Here numbers arrive one at a time as a stream, and after any insertion the current median may be requested. The challenge is maintaining a structure that supports both efficient insertion and fast median retrieval.
One approach keeps a sorted list and inserts each number into its correct position. That gives O(1) median access but O(n) insertion because of shifting. Another appends and sorts on every findMedian call, which is O(n log n) per query. Neither scales well with up to 50,000 operations.
We don't need the entire list sorted. We only need the one or two elements at the middle. If we split the data into a lower half and an upper half and can access the largest element of the lower half and the smallest element of the upper half, we have the median.
Key Constraints:
-10^5 <= num <= 10^5→ Values are bounded integers in a small range. The general solution needs a comparison-based structure, but the bounded range allows a counting-based approach (covered in Approach 3 and the follow-up).At most 5 * 10^4 calls→ With up to 50,000 operations, O(n) work per operation reaches 2.5 billion steps in the worst case, which is too slow. O(log n) peraddNumkeeps the total near 50,000 * 16, well within limits.At least one element before findMedian→ The empty case for median queries does not need handling.
Approach 1: Sort on Each Query
Intuition
Keep all numbers in a list, sort it whenever a median is requested, and take the middle. The median of an ordered list is defined by position, so sorting and indexing gives a correct answer with no extra bookkeeping during insertion.
Algorithm
- Maintain a list of all numbers added so far.
- When
addNum(num)is called, appendnumto the list. - When
findMedian()is called, sort the list. - If the list has odd length, return the middle element.
- If the list has even length, return the average of the two middle elements.
Example Walkthrough
Code
- Time Complexity: O(1) for
addNum, O(n log n) forfindMedian. Appending to a list is O(1). Sorting the entire list on each median query costs O(n log n), where n is the number of elements added so far. - Space Complexity: O(n). We store all n elements in a list.
Sorting from scratch on every query repeats work. The next approach maintains a structure that stays partially ordered during insertion, so the middle elements are always available in O(1).
Approach 2: Two Heaps (Max-Heap + Min-Heap)
Intuition
The median depends only on the element(s) at the boundary between the lower half and the upper half of the data. Two heaps maintain exactly that boundary without keeping everything sorted.
Split the numbers into two groups: a lower half and an upper half. Store the lower half in a max-heap, so its root is the largest small number, and store the upper half in a min-heap, so its root is the smallest large number. The median sits at the boundary between these two roots.
Keep the two heaps balanced in size, letting the max-heap (lower half) hold at most one more element than the min-heap. When the total count is odd, the median is the top of the max-heap. When the total count is even, the median is the average of both heap tops.
The two heaps maintain the invariant that every element in the max-heap is less than or equal to every element in the min-heap. Inserting into the max-heap first and then moving its top into the min-heap preserves this: the candidate that crosses over is the current largest of the lower half, which is the only element that could violate the ordering, so passing it up keeps both halves separated. The rebalancing step then moves an element back if the min-heap grew larger, bounding the size difference at 1. With that bound, an odd total leaves the extra element on the max-heap (its root is the median) and an even total splits evenly (the median is the average of the two roots).
Algorithm
- Create two heaps:
maxHeap(lower half) andminHeap(upper half). - For
addNum(num): - Add
numtomaxHeap. - Move the top of
maxHeaptominHeap(this ensures the largest element from the lower half goes to the upper half if needed). - If
minHeaphas more elements thanmaxHeap, move the top ofminHeapback tomaxHeap. - For
findMedian(): - If the heaps are equal size, return the average of both tops.
- Otherwise, return the top of
maxHeap(since it holds one extra element).
Example Walkthrough
Code
- Time Complexity: O(log n) for
addNum, O(1) forfindMedian. EachaddNumperforms at most 3 heap operations (push + pop + conditional push/pop), each O(log n).findMedianreads the heap tops, which is O(1). - Space Complexity: O(n). Both heaps together store all n elements.
Transition to the follow-up: the heap solution treats every value as distinct and unbounded. The constraints fix every value in [-10^5, 10^5], and the follow-up narrows the common case to [0, 100]. When values come from a small fixed range, counting how many times each value appears replaces the heaps entirely.
Approach 3: Bucket Counts (Bounded Value Range)
Intuition
When values are confined to a small range, the data is fully described by a count of how many times each value has appeared. With values in [0, 100], an array counts of 101 entries records the whole stream: counts[v] is how many times v was added. addNum increments one entry in O(1), independent of how many numbers came before.
The median is found by position. If the total count is n, the median element(s) sit at rank (n - 1) / 2 for odd n, or at ranks n/2 - 1 and n/2 for even n. Walking the count array from the smallest value and accumulating counts locates the value at any target rank, because the array is ordered by value.
Algorithm
- Keep an array
countssized to the value range and a runningtotal. - For
addNum(num): incrementcounts[num]andtotal. - For
findMedian(): - If
totalis odd, scan from the smallest value, accumulating counts until the running sum exceeds ranktotal / 2. Return that value. - If
totalis even, find the values at rankstotal / 2 - 1andtotal / 2in one left-to-right scan and return their average.
The scan to find a value at a given rank moves through the count array. The range is fixed, so this scan is bounded by the range size rather than n.
Example Walkthrough
Code
The implementations below cover the full constraint range [-10^5, 10^5] by offsetting each value by 100000, giving an array of 200001 buckets. For the [0, 100] follow-up, the same code shrinks to 101 buckets with no offset.
- Time Complexity: O(1) for
addNum, O(R) forfindMedian, where R is the size of the value range. Incrementing a count is O(1). Each median query scans the count array, which is bounded by R, not by the number of elements n. For the[0, 100]range R is 101; for the full[-10^5, 10^5]range R is 200001. - Space Complexity: O(R). The count array has one entry per possible value, independent of n.
This approach answers both follow-ups. When all values fall in [0, 100], R is small and a median query is fast. When 99% of values fall in [0, 100] and the rest are outliers, a hybrid keeps a count array for the common range and a separate structure (such as the two heaps from Approach 2) for the rare out-of-range values, combining the ranks from both when locating the median.