Approach Summary
Maintain a max-heap for the lower half and min-heap for the upper half. Balance their sizes; median is the top of the larger or average of both tops.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Insertion Sort (Sorted Vector / Array) | O(N) per addNum, O(1) findMedian | O(N) | Inserts elements into a dynamic array maintaining sorted order via binary search, finding the median in O(1) time. |
| 2 Approach 2: Two Heaps (Max-Heap & Min-Heap) (Optimal) | O(log N) per addNum, O(1) findMedian | O(N) | Divides data stream into a lower half max-heap and an upper half min-heap, balancing their sizes for O(log N) insertion and O(1) median lookup. |
Step 1: Baseline
Approach 1: Insertion Sort (Sorted Vector / Array)
Time: O(N) per addNum, O(1) findMedian
Space: O(N)
1. Maintain a single sorted dynamic array `arr`. 2. In `addNum(num)`: use binary search (`bisect` or `lower_bound`) to find insertion index in O(log N) time, then shift elements to insert `num` in O(N) time. 3. In `findMedian()`: if size is odd, return `arr[n / 2]`; if even, return `(arr[n/2 - 1] + arr[n/2]) / 2.0` in O(1) time. 4. Excellent when queries far outnumber additions, but O(N) insertion is too slow for very large streams.
Approach 1: Insertion Sort (Sorted Vector / Array) Implementation
Approach 1: Insertion Sort (Sorted Vector / Array)
class MedianFinder {
private List<Integer> list = new ArrayList<>();
public void addNum(int num) {
int idx = Collections.binarySearch(list, num);
if (idx < 0) idx = -(idx + 1);
list.add(idx, num);
}
public double findMedian() {
int n = list.size();
if (n % 2 == 1) return list.get(n / 2);
return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
}
}class MedianFinder {
vector<int> arr;
public:
void addNum(int num) {
auto it = lower_bound(arr.begin(), arr.end(), num);
arr.insert(it, num);
}
double findMedian() {
int n = arr.size();
if (n % 2 == 1) return arr[n / 2];
return (arr[n / 2 - 1] + arr[n / 2]) / 2.0;
}
};import bisect
class MedianFinder:
def __init__(self):
self.arr = []
def addNum(self, num: int) -> None:
bisect.insort(self.arr, num)
def findMedian(self) -> float:
n = len(self.arr)
mid = n // 2
if n % 2 == 1:
return float(self.arr[mid])
return (self.arr[mid - 1] + self.arr[mid]) / 2.0var MedianFinder = function() {
this.arr = [];
};
MedianFinder.prototype.addNum = function(num) {
let low = 0, high = this.arr.length;
while (low < high) {
const mid = (low + high) >> 1;
if (this.arr[mid] < num) low = mid + 1;
else high = mid;
}
this.arr.splice(low, 0, num);
};
MedianFinder.prototype.findMedian = function() {
const n = this.arr.length;
const mid = Math.floor(n / 2);
return n % 2 === 1 ? this.arr[mid] : (this.arr[mid - 1] + this.arr[mid]) / 2.0;
}; Step 2: Most Optimized
Approach 2: Two Heaps (Max-Heap & Min-Heap) (Optimal)
Time: O(log N) per addNum, O(1) findMedian
Space: O(N)
1. `maxHeap` stores the lower half of numbers (inverted in Python, standard max-heap in Java/C++). 2. `minHeap` stores the upper half of numbers. 3. In `addNum(num)`: - Push to `maxHeap` if empty or `num <= maxHeap.top()`, else push to `minHeap`. - If size difference exceeds 1, pop from the larger heap and push to the smaller heap. 4. In `findMedian()`: - If `(n1 + n2) % 2 == 0`, median is `(maxHeap.top() + minHeap.top()) / 2.0`. - If odd, median is the top of the heap containing the extra element. 5. Yields optimal O(log N) adds and instantaneous O(1) lookups.
Approach 2: Two Heaps (Max-Heap & Min-Heap) (Optimal) Implementation
Approach 2: Two Heaps (Max-Heap & Min-Heap) (Optimal)
class MedianFinder {
private PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
private PriorityQueue<Integer> large = new PriorityQueue<>();
public void addNum(int num) {
small.add(num);
if (!small.isEmpty() && !large.isEmpty() && small.peek() > large.peek()) {
large.add(small.poll());
}
if (small.size() > large.size() + 1) large.add(small.poll());
if (large.size() > small.size() + 1) small.add(large.poll());
}
public double findMedian() {
if (small.size() > large.size()) return small.peek();
if (large.size() > small.size()) return large.peek();
return (small.peek() + large.peek()) / 2.0;
}
}class MedianFinder {
priority_queue<int> small; // max-heap
priority_queue<int, vector<int>, greater<int>> large; // min-heap
public:
void addNum(int num) {
small.push(num);
if (!small.empty() && !large.empty() && small.top() > large.top()) {
large.push(small.top());
small.pop();
}
if (small.size() > large.size() + 1) {
large.push(small.top());
small.pop();
}
if (large.size() > small.size() + 1) {
small.push(large.top());
large.pop();
}
}
double findMedian() {
if (small.size() > large.size()) return small.top();
if (large.size() > small.size()) return large.top();
return (small.top() + large.top()) / 2.0;
}
};import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (invert values)
self.large = [] # min-heap
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
# Ensure max of small <= min of large
if self.small and self.large and (-self.small[0]) > self.large[0]:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
# Balance sizes
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return float(-self.small[0])
if len(self.large) > len(self.small):
return float(self.large[0])
return (-self.small[0] + self.large[0]) / 2.0class MinHeap {
constructor() { this.heap = []; }
push(val) { this.heap.push(val); this.up(this.heap.length - 1); }
pop() {
if (this.heap.length === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.down(0);
return top;
}
peek() { return this.heap[0]; }
size() { return this.heap.length; }
up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.heap[i] >= this.heap[p]) break;
[this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
i = p;
}
}
down(i) {
const len = this.heap.length;
while (true) {
let smallest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < len && this.heap[l] < this.heap[smallest]) smallest = l;
if (r < len && this.heap[r] < this.heap[smallest]) smallest = r;
if (smallest === i) break;
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
i = smallest;
}
}
}
var MedianFinder = function() {
this.small = new MinHeap(); // will store inverted values for max-heap
this.large = new MinHeap();
};
MedianFinder.prototype.addNum = function(num) {
this.small.push(-num);
if (this.small.size() > 0 && this.large.size() > 0 && -this.small.peek() > this.large.peek()) {
this.large.push(-this.small.pop());
}
if (this.small.size() > this.large.size() + 1) {
this.large.push(-this.small.pop());
}
if (this.large.size() > this.small.size() + 1) {
this.small.push(-this.large.pop());
}
};
MedianFinder.prototype.findMedian = function() {
if (this.small.size() > this.large.size()) return -this.small.peek();
if (this.large.size() > this.small.size()) return this.large.peek();
return (-this.small.peek() + this.large.peek()) / 2.0;
};Edge Cases to Watch
- Single element — median is that single element
- Two elements — median is the arithmetic mean of both elements as a floating point double
- Incoming stream in already sorted order — two heaps balance correctly without performance degradation
- Negative numbers and duplicates — priority queues handle duplicates and negative values natively
Algorithmic Pattern
View Pattern Guide →
Master the Heap / Priority Queue Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Heap / Priority Queue pattern.
Framework: Heap / Priority Queue • Interview Prep: Tested at FAANG •
Explore all Heap / Priority Queue problems & invariants →
How to Recognize This Pattern
- Running median
- Two heaps pattern
Complexity Analysis
Time Complexity
O(log n) add, O(1) median
Space Complexity
O(n)
Tags
Two Heaps Design Sorting
Frequently Asked Questions
What is the optimal time and space complexity for Find Median from Data Stream?
The optimal solution for Find Median from Data Stream achieves O(log n) add, O(1) median runtime complexity and requires O(n) auxiliary space. Time Complexity: `addNum(num)` takes O(log N) time because pushing and popping from either heap of size N/2 requires logarithmic heap adjustment. `findMedian()` takes O(1) time because the median elements reside directly at the top of the two heaps. Space Complexity is O(N) to store all N incoming numbers across the two heaps.
How do I identify that Find Median from Data Stream requires the Heap / Priority Queue pattern?
In technical interviews, look for key problem signals: Running median; Two heaps pattern. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Heap / Priority Queue strategy.
What critical edge cases must be handled in Find Median from Data Stream?
Essential edge cases to verify include: Single element — median is that single element; Two elements — median is the arithmetic mean of both elements as a floating point double; Incoming stream in already sorted order — two heaps balance correctly without performance degradation; Negative numbers and duplicates — priority queues handle duplicates and negative values natively. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Find Median from Data Stream?
Find Median from Data Stream is a Hard-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Google.