295. Find Median from Data Stream

Design a data structure that receives a stream of integers via addNum and returns the median of everything so far via findMedian. Input is a LeetCode-style list of operations.

A max-heap holds the smaller half and a min-heap the larger half, with the max-heap allowed one extra. The median is the max-heap's top, or the average of both tops.

1class MedianFinder {
2  low = new MaxPriorityQueue<number>(); // smaller half
3  high = new MinPriorityQueue<number>(); // larger half
4  addNum(num: number): void {
5    this.low.enqueue(num);
6    this.high.enqueue(this.low.dequeue());
7    if (this.high.size() > this.low.size()) this.low.enqueue(this.high.dequeue());
8  }
9  findMedian(): number {
10    return this.low.size() > this.high.size() ? this.low.front() : (this.low.front() + this.high.front()) / 2;
11  }
12}

op = MedianFinder()

low: max-heap (top first)

empty

high: min-heap (top first)

empty

output

null

Two empty heaps.

1 / 0

Space: play/pause · ←/→: step