Find Median from Data Stream
HardHeaps
Build a MedianFinder class that takes numbers one at a time and can report the median of everything it has seen so far, with two methods:
addNum(num) adds num. findMedian() returns the median: the middle value once the numbers are sorted, or the average of the two middle values when there is an even count of them (so 1, 2, 4, 8 gives 3).
Each test makes a new MedianFinder and calls its methods in order. The output lists what each call returns, with null for the constructor and for addNum.
Examples
Input: MedianFinder(), addNum(5), addNum(1), findMedian(), addNum(9), findMedian() Output: [null, null, null, 3, null, 5]
With 1 and 5 the median is their average, 3. Adding 9 makes 1, 5, 9, whose middle is 5.
Input: MedianFinder(), addNum(-4), findMedian() Output: [null, null, -4]
One number is its own median.
Constraints
-10⁵ ≤ num ≤ 10⁵findMedianis only called after at least oneaddNum.- At most 5 × 10⁴ calls in all.
Stuck?
Hint 1
You never need the numbers fully sorted, only the two in the middle. Split them into a lower half and an upper half.
Hint 2
Keep the lower half in a max-heap and the upper half in a min-heap, with sizes equal or the lower one larger by one. Their tops are the middle values.
The idea
The median only depends on the middle of the sorted numbers, so keep the numbers in two halves: the smaller half in a max-heap and the larger half in a min-heap. Keep every number in the low half at most every number in the high half, and the two sizes within one of each other. Then the middle values sit on top of the two heaps.
Time O(log n) per addNum, O(1) per findMedianExtra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
JavaScript has no built-in heap, so Heap keeps one in an array, with the top at index 0. A new value goes at the end of the array and climbs while it belongs above its parent, which sits at index (i - 1) / 2 rounded down. The heap is only about log n levels tall, so a push takes O(log n).
class Heap { constructor(before) { this.items = []; this.before = before; } get size() { return this.items.length; } peek() { return this.items[0]; } push(value) { const items = this.items; items.push(value); let i = items.length - 1; while (i > 0) { const parent = Math.floor((i - 1) / 2); if (!this.before(items[i], items[parent])) break; [items[i], items[parent]] = [items[parent], items[i]]; i = parent; } } pop() { const items = this.items; const top = items[0]; const last = items.pop(); if (items.length) { items[0] = last; let i = 0; while (true) { const left = 2 * i + 1; const right = left + 1; let best = i; if (left < items.length && this.before(items[left], items[best])) best = left; if (right < items.length && this.before(items[right], items[best])) best = right; if (best === i) break; [items[i], items[best]] = [items[best], items[i]]; i = best; } } return top; }} class MedianFinder { constructor() { this.low = new Heap((a, b) => a > b); this.high = new Heap((a, b) => a < b); } 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.peek(); return (this.low.peek() + this.high.peek()) / 2; }}The trap
Keeping every number in a sorted array and reading the middle looks direct, and it passes while the numbers are all single digits. But sort() with no comparator sorts as text, so 10 comes before 4. As soon as the numbers have different numbers of digits, or a mix of signs, the middle of the array is not the median.
class MedianFinder { constructor() { this.nums = []; } addNum(num) { this.nums.push(num); this.nums.sort(); // sorts as text: 10 comes before 4 } findMedian() { const middle = this.nums.length >> 1; if (this.nums.length % 2) return this.nums[middle]; return (this.nums[middle - 1] + this.nums[middle]) / 2; }}