Heaps
Picture a line of people sorted by height, split into two teams at the middle. The shorter team only watches its tallest member, and the taller team only its shortest. The median is always where the two teams meet, so nobody ever sorts the whole line.
2 · Watch
No sound? Captions are on by default.
3 · Now you drive
Keys:←→ stepSpace playR reset
Find Median from Data Stream
or try
1–8 numbers from -99 to 99, in the order they arrive.Two empty heaps: the lower half on the left, the upper half on the right.Step 1 of 16. Two empty heaps. 4 numbers arriving. No median yet.
Step 1 of 16
solution.ts▶ marks the line running now
class MedianFinder {
low = new MaxHeap(); // smaller half
high = new MinHeap(); // larger half
addNum(num: number) {
this.low.push(num);
this.high.push(this.low.pop());
if (this.high.size() > this.low.size()) {
this.low.push(this.high.pop());
}
}
findMedian(): number {
if (this.low.size() > this.high.size()) return this.low.peek();
return (this.low.peek() + this.high.peek()) / 2;
}
}
4 · Your turn
0 of 1 problems solved
- Hard01
Find Median from Data Stream
The one you just watched. Write it from memory.