295. Find Median From Data Stream
hardAsked at AirbnbDesign a data structure that supports addNum and findMedian in roughly O(log n) and O(1). Airbnb asks this to test the two-heaps trick: a max-heap of the lower half balanced with a min-heap of the upper half.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Airbnb loops.
- Glassdoor (2026-Q1)— Airbnb L4/L5 onsite reports consistently include this as a heap-design hard.
- Blind (2025-12)— Recurring in Airbnb backend and platform team interviews.
Problem
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement the MedianFinder class: MedianFinder() initializes the object; void addNum(int num) adds the integer num from the data stream; double findMedian() returns the median of all elements so far.
Constraints
-10^5 <= num <= 10^5There will be at least one element in the data structure before calling findMedian.At most 5 * 10^4 calls will be made to addNum and findMedian.
Examples
Example 1
addNum(1); addNum(2); findMedian(); addNum(3); findMedian()[null,null,null,1.5,null,2.0]Approaches
1. Sorted array on every add
Maintain a sorted array via binary search insertion. Median is the middle element(s).
- Time
- O(n) per add, O(1) per find
- Space
- O(n)
class MedianFinderArray {
constructor() { this.arr = []; }
addNum(num) {
let lo = 0, hi = this.arr.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.arr[mid] < num) lo = mid + 1;
else hi = mid;
}
this.arr.splice(lo, 0, num);
}
findMedian() {
const n = this.arr.length;
return n % 2 ? this.arr[(n - 1) >> 1] : (this.arr[n / 2 - 1] + this.arr[n / 2]) / 2;
}
}Tradeoff: O(n) per add because splice shifts elements. Acceptable for tiny streams but doesn't scale.
2. Two heaps (optimal)
Max-heap 'lo' holds the lower half; min-heap 'hi' holds the upper half. Keep sizes balanced (lo.size in {hi.size, hi.size + 1}). Median is lo.top() or (lo.top() + hi.top()) / 2.
- Time
- O(log n) per add, O(1) per find
- Space
- O(n)
class MaxHeap {
constructor() { this.data = []; }
push(x) { this.data.push(x); let i = this.data.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.data[p] >= this.data[i]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
top() { return this.data[0]; }
pop() { const t = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; let i = 0; while (true) { let l = 2*i+1, r = 2*i+2, best = i; if (l < this.data.length && this.data[l] > this.data[best]) best = l; if (r < this.data.length && this.data[r] > this.data[best]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } } return t; }
size() { return this.data.length; }
}
class MinHeap {
constructor() { this.data = []; }
push(x) { this.data.push(x); let i = this.data.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (this.data[p] <= this.data[i]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
top() { return this.data[0]; }
pop() { const t = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; let i = 0; while (true) { let l = 2*i+1, r = 2*i+2, best = i; if (l < this.data.length && this.data[l] < this.data[best]) best = l; if (r < this.data.length && this.data[r] < this.data[best]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } } return t; }
size() { return this.data.length; }
}
class MedianFinder {
constructor() { this.lo = new MaxHeap(); this.hi = new MinHeap(); }
addNum(num) {
if (this.lo.size() === 0 || num <= this.lo.top()) this.lo.push(num);
else this.hi.push(num);
if (this.lo.size() > this.hi.size() + 1) this.hi.push(this.lo.pop());
else if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop());
}
findMedian() {
if (this.lo.size() > this.hi.size()) return this.lo.top();
return (this.lo.top() + this.hi.top()) / 2;
}
}Tradeoff: Canonical online-median structure. Each add does at most one cross-heap rebalance. findMedian is O(1) by inspecting tops.
Airbnb-specific tips
Airbnb wants the two-heaps invariant said out loud: 'I split the stream into two halves — a max-heap for the lower half and a min-heap for the upper. Their tops sandwich the median. I keep sizes within 1, rebalancing on each add.' That sentence is the whole answer in narration form.
Common mistakes
- Letting the two heaps drift more than 1 element apart (findMedian breaks).
- Returning lo.top() when lo and hi have equal sizes (should return the average of both tops).
- Pushing to the wrong heap on borderline values — always compare against lo.top().
Follow-up questions
An interviewer at Airbnb may pivot to one of these next:
- Sliding-window median (LC 480) — remove an arbitrary element from the heap; usually requires a TreeMap or balanced BST.
- What if you needed the K-th element instead of the median? (Two heaps with sizes K and n-K, harder to balance.)
- Memory-constrained streaming median — approximation via quantile sketches.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why two heaps instead of a balanced BST?
Both work. Heaps are simpler in languages without a builtin TreeMap. The key requirement is O(log n) insert and O(1) access to the two middle elements; both data structures give that.
Why max-heap on the lower half?
So the top is the largest of the smaller numbers — the lower median candidate. Symmetric for the min-heap on the upper half.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Find Median From Data Stream and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →