Find Median From Data Stream
The briefingthe full drill, in my own words
The drill: A running data stream needs its median available after every insert — sometimes the exact middle, sometimes the average of the two center values, always without a full re-sort.
Numbers arrive one at a time into a running stream, and after every insert, the structure must be able to report the median of every value seen so far.
When the stream holds an odd count of numbers, the median is the single middle value once sorted; with an even count, it's the average of the two center values.
Insertion and the median query are separate operations that can be called in any interleaving, and each median request has to reflect exactly the numbers inserted up to that point.
- stream length can reach tens of thousands of inserts
- values can repeat and be negative, zero, or positive
- an even-count stream's median averages the two middle values
- each query reflects only numbers inserted so far
The hintstake only what you need
HINT 1 THE NUDGE
Re-sorting the whole stream on every median query is honest but wasteful — most of that sorted order is thrown away a moment later. What's the only part of the order you actually need to keep straight?
HINT 2 THE STRUCTURE
Split the numbers into a lower half and an upper half, kept the same size (or off by one). The median only ever touches the boundary between those two halves.
HINT 3 ONE STEP FROM THE ANSWER
A max-heap holds the lower half, a min-heap holds the upper half. Insert into one, shuffle its top across to the other to keep the sizes balanced — the median is then just the top(s) of the heaps.
Coach's boardthe pattern, step by step
A fresh MedianFinder: two empty heaps, a max-heap for the lower half and a min-heap for the upper half.
The splitstwo paces, two languages
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (values negated) — the lower half
self.large = [] # min-heap — the upper half
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2.0class MedianFinder:
def __init__(self):
self.nums = []
def addNum(self, num: int) -> None:
self.nums.append(num)
def findMedian(self) -> float:
nums = sorted(self.nums)
n = len(nums)
mid = n // 2
if n % 2 == 1:
return float(nums[mid])
return (nums[mid - 1] + nums[mid]) / 2.0class MedianFinder {
private final PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder()); // max-heap, lower half
private final PriorityQueue<Integer> large = new PriorityQueue<>(); // min-heap, upper half
public MedianFinder() {
}
public void addNum(int num) {
small.offer(num);
large.offer(small.poll());
if (large.size() > small.size()) {
small.offer(large.poll());
}
}
public double findMedian() {
if (small.size() > large.size()) {
return small.peek();
}
return (small.peek() + large.peek()) / 2.0;
}
}class MedianFinder {
private final List<Integer> nums = new ArrayList<>();
public MedianFinder() {
}
public void addNum(int num) {
nums.add(num);
}
public double findMedian() {
List<Integer> sorted = new ArrayList<>(nums);
Collections.sort(sorted);
int n = sorted.size();
int mid = n / 2;
if (n % 2 == 1) {
return sorted.get(mid);
}
return (sorted.get(mid - 1) + sorted.get(mid)) / 2.0;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED