295. Find Median from Data Stream
hardAsked at RobinhoodDesign a streaming structure that supports addNum and findMedian. Robinhood asks this because the two-heap pattern maps directly to real-time price-feed statistics and rolling-window analytics on trade data.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Robinhood loops.
- Glassdoor (2026-Q1)— Robinhood SWE-II and senior loop reports cite Find Median From Data Stream as a recurring 45-minute hard round.
- Blind (2025-11)— Robinhood backend trip report names two-heap streaming patterns as a thematic favorite.
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 with addNum(int num) and double findMedian(). findMedian must run in O(log n) (or amortized) per addNum and O(1) per findMedian.
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();1.5, 2.0Explanation: After [1,2], median = (1+2)/2 = 1.5. After [1,2,3], median = 2.
Approaches
1. Sorted array
Keep a sorted array. Insert in O(n). Median is the middle element(s) in O(1).
- Time
- O(n) per add, O(1) per findMedian
- Space
- O(n)
class MedianFinderSorted {
constructor() { this.data = []; }
addNum(num) {
let lo = 0, hi = this.data.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.data[mid] < num) lo = mid + 1; else hi = mid;
}
this.data.splice(lo, 0, num);
}
findMedian() {
const n = this.data.length;
if (n % 2) return this.data[(n - 1) >> 1];
return (this.data[n / 2 - 1] + this.data[n / 2]) / 2;
}
}Tradeoff: Simple but the splice insert is O(n). Mention this, then move to the two-heap optimal.
2. Two heaps — max-heap of lower half + min-heap of upper half (optimal)
Maintain a max-heap of the smaller half and a min-heap of the larger half. Balance sizes after each insert. Median is heap tops.
- Time
- O(log n) per add, O(1) per findMedian
- Space
- O(n)
class MinHeap {
constructor() { this.data = []; }
size() { return this.data.length; }
peek() { return this.data[0]; }
push(v) { this.data.push(v); this._up(this.data.length - 1); }
pop() { const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
_up(i) { 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; } }
_down(i) { const n = this.data.length; while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < n && this.data[l] < this.data[best]) best = l; if (r < n && 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; } }
}
class MaxHeap extends MinHeap {
_up(i) { 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; } }
_down(i) { const n = this.data.length; while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < n && this.data[l] > this.data[best]) best = l; if (r < n && 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; } }
}
class MedianFinder {
constructor() {
this.lo = new MaxHeap(); // lower half
this.hi = new MinHeap(); // upper half
}
addNum(num) {
this.lo.push(num);
this.hi.push(this.lo.pop());
if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop());
}
findMedian() {
if (this.lo.size() > this.hi.size()) return this.lo.peek();
return (this.lo.peek() + this.hi.peek()) / 2;
}
}Tradeoff: O(log n) add and O(1) median. The standard interview answer. The two-step add (push to lo, move top to hi, rebalance) keeps the size invariant clean.
Robinhood-specific tips
Robinhood will probably ask the follow-up: what if 99% of values fall in [0, 100]? Answer: bucket them in a counting array of size 101 — O(1) add and O(constant) median. Be ready to sketch that. Also be ready to discuss thread-safety briefly — in a price-feed context the readers and writers are different threads.
Common mistakes
- Maintaining the wrong size invariant (allowing |lo| - |hi| > 1) — breaks the O(1) median lookup.
- Forgetting to rebalance after a single push: you must push to lo, then move lo.top() to hi, then rebalance if hi is now larger.
- Returning an int when the average of two ints is needed; coerce to double via / 2 (JS handles this automatically).
Follow-up questions
An interviewer at Robinhood may pivot to one of these next:
- Sliding-Window Median (LC 480) — extends to remove-too with a delayed-deletion heap or multiset.
- Median in a stream with constrained range — counting-array bucket trick.
- Distributed median over many shards — sketch t-digest or approximate quantiles.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why two heaps instead of one balanced BST?
A balanced BST works (O(log n) add + O(log n) median by rank query) but is significantly more code under interview pressure. Two heaps are the cleanest. If the interviewer asks, mention the BST option.
How does the two-step add keep heaps balanced?
Pushing to lo first then moving lo.top() to hi guarantees the partition is sorted: everything in lo <= everything in hi. The final rebalance ensures |lo| - |hi| ∈ {0, 1}.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Find Median from Data Stream and other Robinhood interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →