Find Median from Data Stream
Mahabharata — The Living Balance — Maintaining the Median as Warriors Keep Arriving
बहाव में माध्य — हमेशा तैयार। दो ढेर — निम्न-अर्ध और उच्च-अर्ध॥
*Median in a stream — always ready. Two heaps — lower half and upper half.*
The Story
Design a data structure that supports adding numbers and finding the median at any time.
MedianFinder.addNum(1) → Median=1 MedianFinder.addNum(2) → Median=1.5 MedianFinder.addNum(3) → Median=2
**Two-Heap Approach:** - `lo`: max-heap for the lower half of all numbers - `hi`: min-heap for the upper half of all numbers - Invariant: `lo.size() >= hi.size()` and `lo.size() - hi.size() <= 1` - Median = lo.peek() (odd count) or (lo.peek() + hi.peek()) / 2.0 (even count)
**addNum:** 1. Add to lo (max-heap) 2. Move lo's max to hi (ensures lo.max ≤ hi.min) 3. If hi has more elements: move hi's min back to lo (rebalance)
```java void addNum(int num) { lo.offer(num); // Always add to lo first hi.offer(lo.poll()); // Move lo's max to hi (cross-pollinate) if (lo.size() < hi.size()) lo.offer(hi.poll()); // Rebalance } double findMedian() { if (lo.size() > hi.size()) return lo.peek(); return (lo.peek() + hi.peek()) / 2.0; } ```
Trace: add 1,2,3 - add(1): lo=[1]. hi.offer(lo.poll())=hi.offer(1)=[1]. lo empty < hi → lo.offer(hi.poll()=1)=[1]. State: lo=[1], hi=[] - add(2): lo=[2,1]. hi.offer(lo.poll()=2)=[2]. lo=[1], lo.size=1≥hi.size=1. State: lo=[1], hi=[2] - add(3): lo=[3,1]. hi.offer(lo.poll()=3)=[3,2]. lo=[1] size=1<hi.size=2 → lo.offer(hi.poll()=2)=[2,1]. State: lo=[2,1], hi=[3] - median: lo.size>hi.size → return lo.peek()=2 ✓
The Sorted-List Approach
Maintain a sorted list. Binary search insert O(log n) + shift O(n). Median in O(1). O(n) per insert overall.
class MedianFinder {
List<Integer> list = new ArrayList<>();
void addNum(int num) {
int pos = Collections.binarySearch(list, num);
if (pos < 0) pos = -(pos+1);
list.add(pos, num);
}
double findMedian() {
int n=list.size();
return n%2==1?list.get(n/2):(list.get(n/2-1)+list.get(n/2))/2.0;
}
}The Two-Heap Balance Wisdom
class MedianFinder {
PriorityQueue<Integer> lo = new PriorityQueue<>((a, b) -> b - a); // Max-heap
PriorityQueue<Integer> hi = new PriorityQueue<>(); // Min-heap
public void addNum(int num) {
lo.offer(num);
hi.offer(lo.poll()); // Move lo's max to hi
if (lo.size() < hi.size()) lo.offer(hi.poll()); // Rebalance
}
public double findMedian() {
if (lo.size() > hi.size()) return lo.peek();
return (lo.peek() + hi.peek()) / 2.0;
}
}Step-by-Step Walkthrough
add(1),add(1),add(1) add(1): lo=[1],hi=[] add(1): lo=[1],hi=[1]. Balanced. add(1): lo=[1,1],hi=[1]. lo>hi → median=1.0 findMedian=1.0 ✅
Deep Insight
**The cross-pollinate step:** `hi.offer(lo.poll())` is the key. It ensures that the maximum of lo always moves to hi before rebalancing. This maintains the crucial invariant: every element in lo ≤ every element in hi. Without this, the two halves could interleave incorrectly.
**Invariant maintained:** After each addNum: - lo.size = hi.size OR lo.size = hi.size + 1 - max(lo) ≤ min(hi)
**Extension:** For hp-17 (Sliding Window Median), add lazy deletion to handle elements leaving the window.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) per insert | O(n) | Sorted list with insertion |
| Optimal | O(log n) per insert, O(1) findMedian | O(n) | Two balanced heaps |
Pattern Recognition
✅ Two heaps: max-heap (lo) + min-heap (hi) ✅ addNum: lo.offer → hi.offer(lo.poll()) → rebalance ✅ findMedian: lo.peek() if lo larger, else average ✅ Invariant: lo.size >= hi.size and all lo ≤ all hi **LeetCode Trigger Phrases:** → "find median from data stream" → Online median maintenance → Two-heap balanced structure
Bhagavad Gita 2.38
सुखदुःखे समे कृत्वा लाभालाभौ जयाजयौ। ततो युद्धाय युज्यस्व नैवं पापमवाप्स्यसि॥
Treating alike pleasure and pain, gain and loss, victory and defeat — engage in battle. Thus you shall incur no sin.
Connection: The median represents perfect balance — the point where half the values are above and half below. The two-heap structure continuously maintains this balance as new numbers arrive: low values gather in lo's max-heap, high values in hi's min-heap, and the boundary between them (the heap tops) gives the median. Like the equanimous warrior treating victory and defeat equally, the structure maintains perfect equilibrium regardless of which values arrive.