295. Find Median from Data Stream (Hard)

Problem

Design a data structure that supports:

• addNum(num), add an integer to the data stream.
• findMedian(), return the median of all elements so far.

Example

addNum(1); addNum(2); findMedian()  // 1.5
addNum(3); findMedian()              // 2.0

LeetCode 295 · Link · Hard

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, store and sort on each findMedian

Keep all values; sort on query.

Python

class MedianFinder:
    def __init__(self):
        self.nums = []
    def addNum(self, num):
        self.nums.append(num)          # L1: O(1) append
    def findMedian(self):
        s = sorted(self.nums)          # L2: O(n log n) sort on every query
        n = len(s)
        if n % 2:
            return s[n // 2]
        return (s[n // 2 - 1] + s[n // 2]) / 2

TypeScript

class MedianFinder {
    private nums: number[] = [];
    addNum(num: number): void {
        this.nums.push(num);           // L1: O(1) append
    }
    findMedian(): number {
        const s = [...this.nums].sort((a, b) => a - b);  // L2: O(n log n) sort on every query
        const n = s.length;
        if (n % 2 === 1) return s[Math.floor(n / 2)];
        return (s[n / 2 - 1] + s[n / 2]) / 2;
    }
}

Go

import "sort"

type MedianFinder struct{ nums []int }

func Constructor() MedianFinder { return MedianFinder{} }

func (mf *MedianFinder) AddNum(num int) {
    mf.nums = append(mf.nums, num) // L1: O(1) append
}

func (mf *MedianFinder) FindMedian() float64 {
    s := make([]int, len(mf.nums))
    copy(s, mf.nums)
    sort.Ints(s)           // L2: O(n log n) sort on every query
    n := len(s)
    if n%2 == 1 { return float64(s[n/2]) }
    return float64(s[n/2-1]+s[n/2]) / 2
}

Swift

final class MedianFinder {
    private var values: [Int] = []
    init() {}
    func addNum(_ num: Int) { values.append(num) }
    func findMedian() -> Double {
        let sorted = values.sorted()
        let middle = sorted.count / 2
        if sorted.count % 2 == 1 { return Double(sorted[middle]) }
        return Double(sorted[middle - 1] + sorted[middle]) / 2.0
    }
}

Where the time goes, line by line

Variables: n = number of elements added so far.

Line	Per-call cost	Times executed	Contribution per call
L1 (addNum append)	$O(1)$	1 per addNum	$O(1)$
L2 (findMedian sort)	$O(n log n)$	1 per findMedian	$O(n log n)$ ← dominates

Complexity

• addNum: $O(1)$ (L1).
• findMedian: $O(n log n)$ (L2).
• Space: $O(n)$.

Approach 2: Insertion sort via bisect.insort

Keep the array sorted on insertion.

Python

import bisect

class MedianFinder:
    def __init__(self):
        self.nums = []
    def addNum(self, num):
        bisect.insort(self.nums, num)   # L1: O(log n) find + O(n) shift
    def findMedian(self):
        n = len(self.nums)
        if n % 2:
            return self.nums[n // 2]    # L2: O(1) index
        return (self.nums[n // 2 - 1] + self.nums[n // 2]) / 2

TypeScript

class MedianFinder {
    private nums: number[] = [];
    addNum(num: number): void {
        // Binary search for insertion point, then splice
        let lo = 0, hi = this.nums.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.nums[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        this.nums.splice(lo, 0, num);   // L1: O(log n) search + O(n) shift
    }
    findMedian(): number {
        const n = this.nums.length;
        if (n % 2 === 1) return this.nums[Math.floor(n / 2)];  // L2: O(1) index
        return (this.nums[n / 2 - 1] + this.nums[n / 2]) / 2;
    }
}

Go

import "sort"

type MedianFinder struct{ nums []int }

func Constructor() MedianFinder { return MedianFinder{} }

func (mf *MedianFinder) AddNum(num int) {
    // Binary search for insertion point, then insert
    i := sort.SearchInts(mf.nums, num)
    mf.nums = append(mf.nums, 0)
    copy(mf.nums[i+1:], mf.nums[i:]) // L1: O(log n) search + O(n) shift
    mf.nums[i] = num
}

func (mf *MedianFinder) FindMedian() float64 {
    n := len(mf.nums)
    if n%2 == 1 { return float64(mf.nums[n/2]) } // L2: O(1) index
    return float64(mf.nums[n/2-1]+mf.nums[n/2]) / 2
}

Swift

final class MedianFinder {
    private var values: [Int] = []
    init() {}
    func addNum(_ num: Int) {
        var low = 0
        var high = values.count
        while low < high { let middle = (low + high) / 2; if values[middle] < num { low = middle + 1 } else { high = middle } }
        values.insert(num, at: low)
    }
    func findMedian() -> Double {
        let middle = values.count / 2
        if values.count % 2 == 1 { return Double(values[middle]) }
        return Double(values[middle - 1] + values[middle]) / 2.0
    }
}

Where the time goes, line by line

Variables: n = number of elements added so far.

Line	Per-call cost	Times executed	Contribution per call
L1 (insort / splice)	$O(n)$	1 per addNum	$O(n)$ ← dominates addNum
L2 (findMedian index)	$O(1)$	1 per findMedian	$O(1)$

bisect.insort / splice uses binary search ($O(log n)$) to find the insertion point but then shifts all elements after it ($O(n)$).

Complexity

• addNum: $O(n)$ (L1 shift dominates).
• findMedian: $O(1)$ (L2).
• Space: $O(n)$.

Approach 3: Two heaps (canonical, optimal)

Maintain a max-heap lo for the smaller half and a min-heap hi for the larger half. Balance them so len(lo) == len(hi) or len(lo) == len(hi) + 1. The median is at the top(s).

Python

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (negated)
        self.hi = []   # min-heap

    def addNum(self, num):
        heapq.heappush(self.lo, -num)                     # L1: O(log n) push to lo
        # Push the largest of `lo` into `hi`
        heapq.heappush(self.hi, -heapq.heappop(self.lo))  # L2: O(log n) pop+push
        # Rebalance: lo should be at least as large as hi
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))  # L3: O(log n) rebalance

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]           # L4: O(1) read lo top
        return (-self.lo[0] + self.hi[0]) / 2  # L5: O(1) average both tops

TypeScript

class MinHeap {
    protected data: number[] = [];
    get size(): number { return this.data.length; }
    get top(): number { return this.data[0]; }
    push(val: number): void {
        this.data.push(val);
        this._siftUp(this.data.length - 1);
    }
    pop(): number {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) { this.data[0] = last; this._siftDown(0); }
        return top;
    }
    protected _siftUp(i: number): void {
        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;
        }
    }
    protected _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l] < this.data[smallest]) smallest = l;
            if (r < n && this.data[r] < this.data[smallest]) smallest = r;
            if (smallest === i) break;
            [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]]; i = smallest;
        }
    }
}

class MaxHeap extends MinHeap {
    protected override _siftUp(i: number): void {
        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;
        }
    }
    protected override _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let largest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l] > this.data[largest]) largest = l;
            if (r < n && this.data[r] > this.data[largest]) largest = r;
            if (largest === i) break;
            [this.data[largest], this.data[i]] = [this.data[i], this.data[largest]]; i = largest;
        }
    }
}

class MedianFinder {
    private lo = new MaxHeap(); // smaller half
    private hi = new MinHeap(); // larger half

    addNum(num: number): void {
        this.lo.push(num);                          // L1: O(log n) push to lo
        this.hi.push(this.lo.pop());               // L2: O(log n) pop lo top + push hi
        if (this.hi.size > this.lo.size)
            this.lo.push(this.hi.pop());           // L3: O(log n) rebalance
    }

    findMedian(): number {
        if (this.lo.size > this.hi.size)
            return this.lo.top;                    // L4: O(1) read lo top
        return (this.lo.top + this.hi.top) / 2;   // L5: O(1) average both tops
    }
}

Go

package main

import (
    "container/heap"
    "fmt"
)

type MaxHeap []int
func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

type MinHeap []int
func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

type MedianFinder struct {
    lo *MaxHeap // smaller half
    hi *MinHeap // larger half
}

func Constructor() MedianFinder {
    lo := &MaxHeap{}; hi := &MinHeap{}; heap.Init(lo); heap.Init(hi)
    return MedianFinder{lo: lo, hi: hi}
}

func (mf *MedianFinder) AddNum(num int) {
    heap.Push(mf.lo, num)                              // L1: O(log n) push to lo
    heap.Push(mf.hi, heap.Pop(mf.lo).(int))           // L2: O(log n) pop+push
    if mf.hi.Len() > mf.lo.Len() {
        heap.Push(mf.lo, heap.Pop(mf.hi).(int))       // L3: O(log n) rebalance
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    if mf.lo.Len() > mf.hi.Len() { return float64((*mf.lo)[0]) } // L4: O(1)
    return float64((*mf.lo)[0]+(*mf.hi)[0]) / 2                   // L5: O(1)
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    mf := Constructor(); mf.AddNum(1); mf.AddNum(2)
    assert(mf.FindMedian() == 1.5); mf.AddNum(3); assert(mf.FindMedian() == 2.0)
    mf2 := Constructor(); mf2.AddNum(42); assert(mf2.FindMedian() == 42.0)
    mf3 := Constructor()
    for _, v := range []int{5, 3, 8, 1, 9} { mf3.AddNum(v) }
    assert(mf3.FindMedian() == 5.0)
    mf4 := Constructor()
    for _, v := range []int{2, 4, 6, 8} { mf4.AddNum(v) }
    assert(mf4.FindMedian() == 5.0)
    fmt.Println("all tests pass")
}

func main() { runTests() }

Swift

final class MedianFinder {
    private var lower = BinaryHeap<Int>(hasHigherPriority: >)
    private var upper = BinaryHeap<Int>(hasHigherPriority: <)
    init() {}
    func addNum(_ num: Int) {
        if let top = lower.peek, num > top { upper.insert(num) } else { lower.insert(num) }
        if lower.count > upper.count + 1 { upper.insert(lower.removeRoot()!) }
        if upper.count > lower.count { lower.insert(upper.removeRoot()!) }
    }
    func findMedian() -> Double {
        if lower.count == upper.count { return Double(lower.peek! + upper.peek!) / 2.0 }
        return Double(lower.peek!)
    }
}

Where the time goes, line by line

Variables: n = number of elements added so far.

Line	Per-call cost	Times executed	Contribution per call
L1 (push to lo)	$O(log n)$	1 per addNum	$O(log n)$ ← dominates addNum
L2 (pop lo + push hi)	$O(log n)$	1 per addNum	$O(log n)$
L3 (rebalance, conditional)	$O(log n)$	up to 1 per addNum	$O(log n)$
L4-L5 (findMedian)	$O(1)$	1 per findMedian	$O(1)$

Each addNum does at most 3 heap operations, each $O(log n)$. The heaps together hold all n elements, so heap size is $O(n)$. The median read is always $O(1)$ because it only looks at the tops.

Complexity

• addNum: $O(log n)$, driven by L1-L3.
• findMedian: $O(1)$ (L4 or L5).
• Space: $O(n)$.

Invariant

After each addNum:

• Every element in lo ≤ every element in hi.
• len(lo) ∈ {len(hi), len(hi) + 1}.

If the total count is odd, the median is lo’s top; if even, it’s the average of both tops.

Try this approach:

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_295.py and run.
# Uses the two-heaps approach (Approach 3).
import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []
        self.hi = []

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0

def _run_tests():
    # Example from problem statement
    mf = MedianFinder()
    mf.addNum(1); mf.addNum(2)
    assert mf.findMedian() == 1.5
    mf.addNum(3)
    assert mf.findMedian() == 2.0

    # Single element
    mf2 = MedianFinder()
    mf2.addNum(42)
    assert mf2.findMedian() == 42.0

    # Odd count median
    mf3 = MedianFinder()
    for v in [5, 3, 8, 1, 9]:
        mf3.addNum(v)
    # sorted: [1,3,5,8,9] -> median = 5
    assert mf3.findMedian() == 5.0

    # Even count median
    mf4 = MedianFinder()
    for v in [2, 4, 6, 8]:
        mf4.addNum(v)
    # sorted: [2,4,6,8] -> median = (4+6)/2 = 5.0
    assert mf4.findMedian() == 5.0

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

// Uses the two-heaps approach (Approach 3).
// See 295-find-median-from-datastream-approach3.ts for the full implementation.
const mf = new MedianFinder();
mf.addNum(1); mf.addNum(2);
console.assert(mf.findMedian() === 1.5);
mf.addNum(3);
console.assert(mf.findMedian() === 2.0);

const mf2 = new MedianFinder();
mf2.addNum(42);
console.assert(mf2.findMedian() === 42.0);

const mf3 = new MedianFinder();
for (const v of [5, 3, 8, 1, 9]) mf3.addNum(v);
console.assert(mf3.findMedian() === 5.0);  // sorted: [1,3,5,8,9]

const mf4 = new MedianFinder();
for (const v of [2, 4, 6, 8]) mf4.addNum(v);
console.assert(mf4.findMedian() === 5.0);  // (4+6)/2

console.log("all tests pass");

Summary

Approach	addNum	findMedian	Space
Append + sort on query	$O(1)$	$O(n log n)$	$O(n)$
Insertion sort	$O(n)$	$O(1)$	$O(n)$
Two heaps	$O(log n)$	$O(1)$	$O(n)$

The two-heap technique is one of the most important design patterns in interviews. It also powers the sliding-window median (480) and percentile-tracking streaming systems.

Related data structures

• Heaps / Priority Queues, balanced dual-heap for running median

Related concepts

• Heap and Priority Queue, priority-frontier tactics for repeatedly extracting the smallest, largest, or most urgent item.
• K-way Merge, multi-stream ordering tactics for combining several sorted sources through one priority queue.