Find Median from Data Stream solution and explanation
9 more videos on this problem
Find Median from Data Stream - Heap & Priority Queue - Leetcode 295NeetCode · 23:35 · 286K views
Find Median from Data Stream | Detailed Explanation | Leetcode 295 | codestorywithMIKcodestorywithMIK · 36:44 · 69K views
Leetcode 295. Find Median from Data Stream Intuition + Code C++ ExampleCode with Alisha · 27:59 · 9K views
FIND MEDIAN FROM DATA STREAM | LEETCODE # 295 | PYTHON TWO HEAPS SOLUTIONCracking FAANG · 24:26 · 4K views
[Java] Leetcode 295. Find Median from Data Stream [Two Heaps #1]Eric Programming · 10:21 · 4K views
Find Median from Data Stream: Real-Time Median with Heaps | LeetCode 295 | GeekificGeekific · 5:05 · 2K views
Find Median From Data Stream - LeetCode 295 - Apple InterviewAlgoJS · 5:49 · 1K views
Mock Interview | 295 Find Median from Data StreamFraz · 29:32 · 1K views
LeetCode 295. Find Median from Data StreamSrinu Nampalli @Algo2Design · 7:41 · 850 views
Find Median From Data Stream | LeetCode 295 (Hard)Destination FAANG · 29:40 · 696 views
The 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.
- For example, for
arr = [2,3,4], the median is3. - For example, for
arr = [2,3], the median is(2 + 3) / 2 = 2.5.
Implement the MedianFinder class:
MedianFinder()initializes theMedianFinderobject.void addNum(int num)adds the integernumfrom the data stream to the data structure.double findMedian()returns the median of all elements so far. Answers within10-5of the actual answer will be accepted.
Example 1:
Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
Constraints:
-105 <= num <= 105- There will be at least one element in the data structure before calling
findMedian. - At most
5 * 104calls will be made toaddNumandfindMedian.
Follow up:
- If all integer numbers from the stream are in the range
[0, 100], how would you optimize your solution? - If
99%of all integer numbers from the stream are in the range[0, 100], how would you optimize your solution?
Approach overview
Problem Overview: Design a data structure that continuously receives numbers from a stream and returns the median at any moment. After each insertion, you must efficiently compute the middle value of all elements seen so far.
Approach 1: Two Heaps (Min-Heap + Max-Heap) (Insertion: O(log n), Median: O(1))
The optimal solution maintains two heaps that split the dataset into two halves. A max-heap stores the smaller half of numbers, while a min-heap stores the larger half. This ensures the largest value of the left half and the smallest value of the right half are always accessible. When inserting a number, push it into one heap and rebalance so the size difference never exceeds one. If both heaps have equal size, the median is the average of their top elements; otherwise it is the top of the larger heap. Heap insertions and rebalancing cost O(log n), while retrieving the median is O(1). This technique heavily relies on Heap (Priority Queue) operations and is commonly used in design problems involving streaming data.
Approach 2: Balanced Binary Search Tree (Insertion: O(log n), Median: O(1) or O(log n))
A balanced binary search tree keeps elements sorted as they arrive. Each insertion takes O(log n) because the tree maintains ordering automatically. To retrieve the median efficiently, track pointers (or iterators) to the middle element(s) and update them whenever a new value is inserted. When the number of elements becomes even, the median is the average of the two center values; when odd, it is the middle node. This approach leverages ordered traversal properties of a balanced BST and relates closely to sorting behavior, since the structure always maintains sorted order. Space complexity is O(n) because all numbers must remain stored.
Recommended for interviews: The two-heap strategy is the expected solution. It demonstrates understanding of heap balancing, streaming data handling, and efficient median queries. Discussing the BST approach shows awareness of ordered data structures, but the heap-based design is more common in production systems and coding interviews.
Approach 1: Using Two Heaps (Min-Heap and Max-Heap)
The main idea is to use a max-heap to store the smaller half of the numbers and a min-heap to store the larger half. The max-heap allows you to efficiently fetch the largest element of the smaller half, and the min-heap allows you to efficiently fetch the smallest element of the larger half. To maintain the balance, ensure that the number of elements in the max-heap is either equal to or one more than the number of elements in the min-heap.
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max-heap (inverted to min-heap by storing negative values)
self.large = [] # min-heap
def addNum(self, num: int) -> None:
heapq.heappush(self.small, -num)
if self.small and self.large and (-self.small[0] > self.large[0]):
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
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):
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2import java.util.PriorityQueue;
class MedianFinder {
private PriorityQueue<Integer> small;
private PriorityQueue<Integer> large;
public MedianFinder() {
small = new PriorityQueue<>((a, b) -> b - a);
large = new PriorityQueue<>();
}
public void addNum(int num) {
small.add(num);
large.add(small.poll());
if (small.size() < large.size()) {
small.add(large.poll());
}
}
public double findMedian() {
if (small.size() > large.size()) {
return small.peek();
}
return (small.peek() + large.peek()) / 2.0;
}
}#include <queue>
class MedianFinder {
std::priority_queue<int> small;
std::priority_queue<int, std::vector<int>, std::greater<int>> large;
public:
void addNum(int num) {
small.push(num);
large.push(small.top());
small.pop();
if (small.size() < large.size()) {
small.push(large.top());
large.pop();
}
}
double findMedian() {
if (small.size() > large.size())
return small.top();
return (small.top() + large.top()) / 2.0;
}
};class MedianFinder {
constructor() {
this.small = new MinHeap(); // Max-Heap
this.large = new MinHeap(); // Min-Heap
}
addNum(num) {
this.small.insert(-num);
if (-this.small.peek() > this.large.peek()) {
this.large.insert(-this.small.remove());
}
if (this.small.size() > this.large.size() + 1) {
this.large.insert(-this.small.remove());
}
if (this.large.size() > this.small.size()) {
this.small.insert(-this.large.remove());
}
}
findMedian() {
if (this.small.size() > this.large.size()) return -this.small.peek();
return (-this.small.peek() + this.large.peek()) / 2.0;
}
}
class MinHeap {
constructor() {
this.heap = [];
}
insert(val) {
this.heap.push(val);
this._bubbleUp();
}
peek() {
return this.heap[0] || Infinity;
}
remove() {
if (this.size() < 2) return this.heap.pop() || Infinity;
this._swap(0, this.heap.length - 1);
const popped = this.heap.pop();
this._bubbleDown();
return popped;
}
size() {
return this.heap.length;
}
_bubbleUp() {
let idx = this.heap.length - 1;
const element = this.heap[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
let parent = this.heap[parentIdx];
if (element >= parent) break;
this._swap(parentIdx, idx);
idx = parentIdx;
}
}
_bubbleDown() {
let idx = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftIdx = 2 * idx + 1;
let rightIdx = 2 * idx + 2;
let left, right;
let swap = null;
if (leftIdx < length) {
left = this.heap[leftIdx];
if (left < element) swap = leftIdx;
}
if (rightIdx < length) {
right = this.heap[rightIdx];
if ((swap === null && right < element) || (swap !== null && right < left)) swap = rightIdx;
}
if (swap === null) break;
this._swap(idx, swap);
idx = swap;
}
}
_swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
}The solution uses two heaps (small and large). 'small' is a max-heap that stores the smaller half of the numbers, and 'large' is a min-heap that stores the larger half. Each time a number is added, it is pushed to the max-heap first. If the max-heap's largest is greater than the min-heap's smallest, balance them by moving numbers between heaps. The median can be derived based on the sizes of the heaps.
The time complexity for adding a number is O(log n) due to heap adjustments. Finding the median has a time complexity of O(1). Space complexity is O(n), where n is the number of elements.
Approach 2: Using a Balanced Binary Search Tree
An alternative approach is to use a balanced binary search tree (BST) to keep track of the numbers. This allows maintaining a sorted order of elements, which can make finding the median efficient since a BST can give average-case time complexity of O(log n) for insertion and O(1) for median finding.
using System;
using System.Collections.Generic;
public class MedianFinder {
private SortedSet<(int, int)> small;
private SortedSet<(int, int)> large;
private int counter = 0;
public MedianFinder() {
small = new SortedSet<(int, int)>();
large = new SortedSet<(int, int)>();
}
public void AddNum(int num) {
small.Add((num, counter++));
large.Add(small.Max);
small.Remove(small.Max);
if (large.Count > small.Count) {
small.Add(large.Min);
large.Remove(large.Min);
}
}
public double FindMedian() {
if (small.Count > large.Count) {
return small.Max.Item1;
}
return (small.Max.Item1 + large.Min.Item1) / 2.0;
}
}This C# implementation uses two sorted sets as a stand-in for a balanced BST. Every number is inserted into the smaller set first, followed by balancing between the two sets. The median is retrieved based on the sizes of the sets and their boundary values.
Insertion and balancing in the sorted set take O(log n) time, and findings of the median are O(1). Space complexity is O(n).
Approach 3: Min Heap and Max Heap (Priority Queue)
We can use two heaps to maintain all the elements, a min heap minQ and a max heap maxQ, where the min heap minQ stores the larger half, and the max heap maxQ stores the smaller half.
When calling the addNum method, we first add the element to the max heap maxQ, then pop the top element of maxQ and add it to the min heap minQ. If at this time the size difference between minQ and maxQ is greater than 1, we pop the top element of minQ and add it to maxQ. The time complexity is O(log n).
When calling the findMedian method, if the size of minQ is equal to the size of maxQ, it means the total number of elements is even, and we can return the average value of the top elements of minQ and maxQ; otherwise, we return the top element of minQ. The time complexity is O(1).
The space complexity is O(n), where n is the number of elements.
class MedianFinder {
#minQ = new MinPriorityQueue<number>();
#maxQ = new MaxPriorityQueue<number>();
addNum(num: number): void {
const [minQ, maxQ] = [this.#minQ, this.#maxQ];
maxQ.enqueue(num);
minQ.enqueue(maxQ.dequeue());
if (minQ.size() - maxQ.size() > 1) {
maxQ.enqueue(minQ.dequeue());
}
}
findMedian(): number {
const [minQ, maxQ] = [this.#minQ, this.#maxQ];
if (minQ.size() === maxQ.size()) {
return (minQ.front() + maxQ.front()) / 2;
}
return minQ.front();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/type MedianFinder struct {
minq hp
maxq hp
}
func Constructor() MedianFinder {
return MedianFinder{hp{}, hp{}}
}
func (this *MedianFinder) AddNum(num int) {
minq, maxq := &this.minq, &this.maxq
heap.Push(maxq, -num)
heap.Push(minq, -heap.Pop(maxq).(int))
if minq.Len()-maxq.Len() > 1 {
heap.Push(maxq, -heap.Pop(minq).(int))
}
}
func (this *MedianFinder) FindMedian() float64 {
minq, maxq := this.minq, this.maxq
if minq.Len() == maxq.Len() {
return float64(minq.IntSlice[0]-maxq.IntSlice[0]) / 2
}
return float64(minq.IntSlice[0])
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
/**
* Your MedianFinder object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(num);
* param_2 := obj.FindMedian();
*/class MedianFinder {
private var minQ = Heap<Int>(sort: <)
private var maxQ = Heap<Int>(sort: >)
init() {
}
func addNum(_ num: Int) {
maxQ.insert(num)
minQ.insert(maxQ.remove()!)
if maxQ.count < minQ.count {
maxQ.insert(minQ.remove()!)
}
}
func findMedian() -> Double {
if maxQ.count > minQ.count {
return Double(maxQ.peek()!)
}
return (Double(maxQ.peek()!) + Double(minQ.peek()!)) / 2.0
}
}
struct Heap<T> {
var elements: [T]
let sort: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool, elements: [T] = []) {
self.sort = sort
self.elements = elements
if !elements.isEmpty {
for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
siftDown(from: i)
}
}
}
var isEmpty: Bool {
return elements.isEmpty
}
var count: Int {
return elements.count
}
func peek() -> T? {
return elements.first
}
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func remove() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let removedValue = elements.removeLast()
siftDown(from: 0)
return removedValue
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = parentIndex(ofChildAt: child)
while child > 0 && sort(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = parentIndex(ofChildAt: child)
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = leftChildIndex(ofParentAt: parent)
let right = rightChildIndex(ofParentAt: parent)
var candidate = parent
if left < count && sort(elements[left], elements[candidate]) {
candidate = left
}
if right < count && sort(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent {
return
}
elements.swapAt(parent, candidate)
parent = candidate
}
}
private func parentIndex(ofChildAt index: Int) -> Int {
return (index - 1) / 2
}
private func leftChildIndex(ofParentAt index: Int) -> Int {
return 2 * index + 1
}
private func rightChildIndex(ofParentAt index: Int) -> Int {
return 2 * index + 2
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* let obj = MedianFinder()
* obj.addNum(num)
* let ret_2: Double = obj.findMedian()
*/use std::cmp::Reverse;
use std::collections::BinaryHeap;
struct MedianFinder {
minQ: BinaryHeap<Reverse<i32>>,
maxQ: BinaryHeap<i32>,
}
impl MedianFinder {
fn new() -> Self {
MedianFinder {
minQ: BinaryHeap::new(),
maxQ: BinaryHeap::new(),
}
}
fn add_num(&mut self, num: i32) {
self.maxQ.push(num);
self.minQ.push(Reverse(self.maxQ.pop().unwrap()));
if self.minQ.len() > self.maxQ.len() + 1 {
self.maxQ.push(self.minQ.pop().unwrap().0);
}
}
fn find_median(&self) -> f64 {
if self.minQ.len() == self.maxQ.len() {
let min_top = self.minQ.peek().unwrap().0;
let max_top = *self.maxQ.peek().unwrap();
(min_top + max_top) as f64 / 2.0
} else {
self.minQ.peek().unwrap().0 as f64
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Two Heaps (Min-Heap and Max-Heap) | The time complexity for adding a number is O(log n) due to heap adjustments. Finding the median has a time complexity of O(1). Space complexity is O(n), where n is the number of elements. |
| Using a Balanced Binary Search Tree | Insertion and balancing in the sorted set take O(log n) time, and findings of the median are O(1). Space complexity is O(n). |
| Min Heap and Max Heap (Priority Queue) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Heaps (Min-Heap + Max-Heap) | addNum: O(log n), findMedian: O(1) | O(n) | Best general solution for streaming numbers and interview scenarios |
| Balanced Binary Search Tree | addNum: O(log n), findMedian: O(1)-O(log n) | O(n) | Useful when an ordered structure or iterator access is already required |
Frequently asked questions
Is Find Median from Data Stream easy or hard?
Find Median from Data Stream is classified as a Hard problem because it combines data structure design with efficient real-time updates. Understanding heap balancing and edge cases with even and odd counts is necessary to implement it correctly.
Find Median from Data Stream Python/Java solution
In Python, the solution typically uses the heapq module with a max-heap simulated using negative values. Java implementations often use two PriorityQueue objects, one configured as a max-heap and the other as a min-heap. Both versions maintain balanced heap sizes and compute the median from their top elements.
How to solve Find Median from Data Stream in O(n)?
The typical solution does not aim for total O(n) processing because the stream requires incremental updates. Instead, each insertion is handled in O(log n) using two heaps, giving efficient performance for long streams. A naive approach that re-sorts after each insertion would be much slower at O(n log n) per update.
What is the best approach for Find Median from Data Stream?
The two-heap approach is considered the optimal solution. It keeps the lower half of numbers in a max-heap and the upper half in a min-heap, ensuring both halves remain balanced. Insertion takes O(log n) and retrieving the median takes O(1), which is ideal for continuous data streams.
Is Find Median from Data Stream asked at Google/Amazon/Meta?
Find Median from Data Stream frequently appears in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests data structure design, heap operations, and the ability to maintain running statistics on streaming input.
What data structure is used in Find Median from Data Stream?
The most common data structures are a max-heap and a min-heap working together. Some implementations also use a balanced binary search tree or ordered multiset to maintain sorted order while tracking the median.
What is the time complexity of Find Median from Data Stream?
Using the optimal two-heap design, inserting a number takes O(log n) due to heap insertion and potential rebalancing. Retrieving the median is O(1) because it only checks the top elements of the heaps. Space complexity is O(n) since all values from the stream are stored.