Median in a stream of integers
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]
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.