Median in a stream of integers

Hard

Problem

Numbers arrive one at a time. After each insertion, report the median of everything seen so far. Insertion should be O(log n) and reading the median O(1).

Example 1

Input:  stream 5, 15, 1, 3
Output: 5, 10, 5, 4

Also asked as: Median in a stream of Integers

Test cases

Case 1

Input:    new MedianFinder()
.addNum(1)
.addNum(2)
.findMedian()
.addNum(3)
.findMedian()
Expected: [null,null,1.5,null,2]

Case 2

Input:    new MedianFinder()
.addNum(5)
.findMedian()
.addNum(15)
.findMedian()
.addNum(1)
.findMedian()
.addNum(3)
.findMedian()
Expected: [null,5,null,10,null,5,null,4]

Case 3

Input:    new MedianFinder()
.addNum(2)
.addNum(2)
.findMedian()
Expected: [null,null,2]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two heaps — max-heap for the low half, min-heap for the high half

Time O(log n) per insert, O(1) querySpace O(n)

Keep the halves balanced (sizes differ by ≤ 1). The median is the top of the larger heap, or the average of both tops.

class MedianFinder {
constructor() { this.low = []; this.high = []; } // low is a max-heap, high a min-heap (sorted arrays here)
addNum(x) {
const push = (h, v, cmp) => { let i = h.findIndex((e) => cmp(e, v)); i === -1 ? h.push(v) : h.splice(i, 0, v); };
push(this.low, x, (e, v) => e < v); // descending
this.high.push(this.low.shift());
this.high.sort((a, b) => a - b);
if (this.high.length > this.low.length) { this.low.unshift(this.high.shift()); this.low.sort((a, b) => b - a); }
}
findMedian() {
if (this.low.length > this.high.length) return this.low[0];
return (this.low[0] + this.high[0]) / 2;
}
}

Use real binary heaps for O(log n); the sorted-array version above is O(n) per insert but shows the idea.