Find Median from Data Stream
Find Median from Data Stream is a hard heaps problem solved with the advanced pattern.
The best approach, optimal (two heaps), runs in addNum O(log n), findMedian O(1) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (sort on every query) up.
Problem
Build a MedianFinder class that receives integers one at a time and can report the median of everything it has received so far.
addNum(num)adds the integernumto the collection.findMedian()returns the median as a decimal number: the middle value when the count is odd, or the average of the two middle values when the count is even.
Examples
Example 1
- Input
addNum(7), addNum(3), findMedian(), addNum(5), findMedian(), addNum(10), findMedian()- Output
5.0, 5.0, 6.0- Why
- {3, 7} gives (3 + 7) / 2 = 5.0; {3, 5, 7} gives 5.0; {3, 5, 7, 10} gives (5 + 7) / 2 = 6.0.
Example 2
- Input
addNum(-4), findMedian(), addNum(-4), addNum(9), findMedian()- Output
-4.0, -4.0- Why
- A single value is its own median; {-4, -4, 9} has -4 in the middle.
Constraints
-10^5 <= num <= 10^5findMedianis only called after at least oneaddNum.- At most
5 * 10^4calls in total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (sort on every query) | addNum O(1), findMedian O(n log n) | O(n) |
| Better (keep the list sorted) | addNum O(n), findMedian O(1) | O(n) |
| Optimal (two heaps) | addNum O(log n), findMedian O(1) | O(n) |
1Brute force (sort on every query)
addNum O(1), findMedian O(n log n)Each query sorts all n values again.O(n)The list holds every number, plus a sorted copy during a query.Append each number to a list. When the median is asked for, copy and sort the list and read the middle one or two values.
- addNum appends to the list.
- findMedian sorts a copy of the list.
- Odd size: return the middle value. Even size: return the average of the two middle values.
class MedianFinder {
private final List<Integer> data = new ArrayList<>();
public void addNum(int num) { data.add(num); }
public double findMedian() {
List<Integer> s = new ArrayList<>(data);
Collections.sort(s);
int n = s.size();
if (n % 2 == 1) return s.get(n / 2);
return (s.get(n / 2 - 1) + s.get(n / 2)) / 2.0;
}
}class MedianFinder:
def __init__(self):
self.data = []
def addNum(self, num: int) -> None:
self.data.append(num)
def findMedian(self) -> float:
s = sorted(self.data)
n = len(s)
if n % 2 == 1:
return float(s[n // 2])
return (s[n // 2 - 1] + s[n // 2]) / 2.0class MedianFinder {
vector<int> data;
public:
void addNum(int num) { data.push_back(num); }
double findMedian() {
vector<int> s = data;
sort(s.begin(), s.end());
int n = s.size();
if (n % 2 == 1) return s[n / 2];
return (s[n / 2 - 1] + s[n / 2]) / 2.0;
}
};class MedianFinder {
constructor() {
this.data = [];
}
addNum(num) { this.data.push(num); }
findMedian() {
const s = [...this.data].sort((a, b) => a - b);
const n = s.length;
if (n % 2 === 1) return s[n >> 1];
return (s[n / 2 - 1] + s[n / 2]) / 2;
}
}2Better (keep the list sorted)
addNum O(n), findMedian O(1)The binary search is O(log n), but inserting shifts up to n elements.O(n)The sorted list holds every number.Keep the list sorted at all times. Binary search for where each new number belongs and insert it there, so the median is always one index lookup away.
- addNum: binary search for the first position whose value is >= num, insert num there.
- findMedian: read the middle one or two values directly.
class MedianFinder {
private final List<Integer> s = new ArrayList<>();
public void addNum(int num) {
int lo = 0, hi = s.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (s.get(mid) < num) lo = mid + 1; else hi = mid;
}
s.add(lo, num);
}
public double findMedian() {
int n = s.size();
if (n % 2 == 1) return s.get(n / 2);
return (s.get(n / 2 - 1) + s.get(n / 2)) / 2.0;
}
}class MedianFinder:
def __init__(self):
self.s = []
def addNum(self, num: int) -> None:
lo, hi = 0, len(self.s)
while lo < hi:
mid = (lo + hi) // 2
if self.s[mid] < num:
lo = mid + 1
else:
hi = mid
self.s.insert(lo, num)
def findMedian(self) -> float:
n = len(self.s)
if n % 2 == 1:
return float(self.s[n // 2])
return (self.s[n // 2 - 1] + self.s[n // 2]) / 2.0class MedianFinder {
vector<int> s;
public:
void addNum(int num) {
int lo = 0, hi = s.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (s[mid] < num) lo = mid + 1; else hi = mid;
}
s.insert(s.begin() + lo, num);
}
double findMedian() {
int n = s.size();
if (n % 2 == 1) return s[n / 2];
return (s[n / 2 - 1] + s[n / 2]) / 2.0;
}
};class MedianFinder {
constructor() {
this.s = [];
}
addNum(num) {
let lo = 0, hi = this.s.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.s[mid] < num) lo = mid + 1; else hi = mid;
}
this.s.splice(lo, 0, num);
}
findMedian() {
const n = this.s.length;
if (n % 2 === 1) return this.s[n >> 1];
return (this.s[n / 2 - 1] + this.s[n / 2]) / 2;
}
}3Optimal (two heaps)
addNum O(log n), findMedian O(1)Each add does a constant number of heap pushes and pops, each O(log n).O(n)The two heaps together hold every number.Split the numbers into a lower half and an upper half. A max-heap holds the lower half and a min-heap holds the upper half. The lower heap is allowed one extra element. The median is then either the top of the lower heap, or the average of both tops.
- addNum: push num into the max-heap
low, then move the top oflowinto the min-heaphigh(this keeps every value inlow<= every value inhigh). - If
highis now bigger thanlow, move the top ofhighback intolow. - findMedian: if
lowis bigger, return its top; otherwise return the average of both tops.
class MedianFinder {
private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
private final PriorityQueue<Integer> high = new PriorityQueue<>();
public void addNum(int num) {
low.offer(num);
high.offer(low.poll());
if (high.size() > low.size()) low.offer(high.poll());
}
public double findMedian() {
if (low.size() > high.size()) return low.peek();
return (low.peek() + high.peek()) / 2.0;
}
}class MedianFinder:
def __init__(self):
self.low = [] # max-heap stored as negatives
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 float(-self.low[0])
return (-self.low[0] + self.high[0]) / 2.0class MedianFinder {
priority_queue<int> low; // max-heap
priority_queue<int, vector<int>, greater<int>> high; // min-heap
public:
void addNum(int num) {
low.push(num);
high.push(low.top());
low.pop();
if (high.size() > low.size()) {
low.push(high.top());
high.pop();
}
}
double findMedian() {
if (low.size() > high.size()) return low.top();
return (low.top() + high.top()) / 2.0;
}
};class Heap {
constructor(less) {
this.a = [];
this.less = less;
}
size() { return this.a.length; }
top() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0];
const last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
class MedianFinder {
constructor() {
this.low = new Heap((x, y) => x > y); // max-heap
this.high = new Heap((x, y) => x < y); // min-heap
}
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;
}
}Edge cases to test
- Only one number added so far
- Many equal values
- Numbers arriving in strictly increasing or strictly decreasing order
- An even count, where the median is the average of two values and may end in .5
Hints
Hint 1
Sorting on every query works but repeats a lot of work. What do you really need to know to read the median?
Hint 2
You only need the largest value of the lower half and the smallest value of the upper half.
Hint 3
Keep the lower half in a max-heap and the upper half in a min-heap, and keep their sizes within one of each other.
FAQ
What is the best time complexity for Find Median from Data Stream?
Optimal (two heaps) runs in addNum O(log n), findMedian O(1) time and O(n) extra space. Each add does a constant number of heap pushes and pops, each O(log n).
Which pattern does Find Median from Data Stream use?
It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Trapping Rain Water II, Minimum Number of Refueling Stops.
Is there a brute force solution for Find Median from Data Stream?
Yes. Brute force (sort on every query) takes addNum O(1), findMedian O(n log n) time and O(n) space. Append each number to a list.
Which edge cases should I test for Find Median from Data Stream?
Only one number added so far; Many equal values; Numbers arriving in strictly increasing or strictly decreasing order; An even count, where the median is the average of two values and may end in .5.