—
low.max
Numbers arrive one at a time and you must report the running median on demand. Split the data across two heaps — a max-heap for the smaller half and a min-heap for the larger half — kept balanced so the median always sits right on their tops.
Design a structure with two operations: addNum(x) feeds a number from an infinite stream, and findMedian() returns the median of everything seen so far. The median is the middle value of the sorted data, or the average of the two middle values when the count is even. Stream 5, 2, 8, 1, 9, 4 → after all six, sorted is [1,2,4,5,8,9] so the median is (4 + 5) / 2 = 4.5.
low) and the larger half in a min-heap (high). If their sizes differ by at most one, the median is either the average of the two tops (sizes equal) or the top of the bigger heap. Both tops are O(1) to read.low is empty or x ≤ low.max, push x to low; otherwise push it to high. This keeps every number in low ≤ every number in high.|low| > |high| + 1, move low's max into high. If |high| > |low|, move high's min into low. Now the sizes differ by at most one (with low holding the extra).(low.max + high.min) / 2. Otherwise low is the bigger heap ⇒ median = low.max.low is always the one that grows by one on odd counts, so for an odd total the median is unambiguously low.max — never high.min. Pick a convention and keep the rebalance asymmetric to match it.A sorted array gives O(1) median but each addNum is O(n) for the shift. The two-heap structure trades that for O(log n) inserts while still reading the median in O(1). Space is O(n) to hold the stream. If values are bounded small integers, a Fenwick/BIT or bucket-count approach can also hit O(log n) or O(1) per query.
low holds the smaller half (max on top), high holds the larger half (min on top).class MedianFinder {
// low = max-heap (smaller half), high = min-heap (larger half).
// We keep |low| === |high|, or |low| === |high| + 1.
private low: MaxHeap = new MaxHeap();
private high: MinHeap = new MinHeap();
addNum(num: number): void {
// 1. Route by value so low always holds the smaller numbers.
if (this.low.size === 0 || num <= this.low.peek()) this.low.push(num);
else this.high.push(num);
// 2. Rebalance so the two sizes differ by at most one.
if (this.low.size > this.high.size + 1) {
this.high.push(this.low.pop());
} else if (this.high.size > this.low.size) {
this.low.push(this.high.pop());
}
}
findMedian(): number {
if (this.low.size === this.high.size) {
// Even count: average the two middle elements (the heap tops).
return (this.low.peek() + this.high.peek()) / 2;
}
// Odd count: low carries the extra element, so its top IS the median.
return this.low.peek();
}
}low is a max-heap holding the smaller half, so its top is the largest of the small numbers. high is a min-heap holding the larger half, so its top is the smallest of the big numbers. The invariant is |low| === |high| or |low| === |high| + 1.low.peek()) belongs to the smaller half, so it goes into low; everything else goes into high. The empty-low case sends the very first number to low.low or the min of high) restores the size invariant. The asymmetric checks (> high.size + 1 vs > low.size) ensure low is the heap that carries the extra element on odd counts.low holds the extra, the single middle element is low.peek().addNum is O(log n) (one or two heap operations); findMedian is O(1) (read one or two tops). Space is O(n) to store the stream.| running / streaming median | two heaps (max-heap + min-heap) |
| need the middle without full sort | balanced partition at the boundary |
| sizes off by 2 after insert | move one element across to rebalance |
| sliding-window median | two heaps + lazy deletion |
// low = max-heap (smaller half), high = min-heap (larger half)
addNum(num) {
if (low.size === 0 || num <= low.peek()) low.push(num);
else high.push(num);
if (low.size > high.size + 1) high.push(low.pop());
else if (high.size > low.size) low.push(high.pop());
}
findMedian() {
if (low.size === high.size) return (low.peek() + high.peek()) / 2;
return low.peek();
}low = max-heap for the smaller half (top is its largest); high = min-heap for the larger half (top is its smallest).