HardBlind75Two HeapsDesignSort

Find Median from Data Stream

Design a data structure that supports addNum and findMedian operations.

Examples

Input
MedianFinder.addNum(1); MedianFinder.addNum(2); MedianFinder.findMedian(); MedianFinder.addNum(3); MedianFinder.findMedian()
Output
1.5, 2.0

After adding 1 and 2, median is 1.5. After adding 3, median is 2.0.

Constraints

  • •-10^5 <= num <= 10^5
  • •There 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.

Approaches

Store all numbers in a sorted list. Find median by index.

CodeT: O(n) add, O(1) find | S: O(n)
import bisect

class MedianFinder:
    def __init__(self):
        self.nums = []
    def addNum(self, num):
        bisect.insort(self.nums, num)
    def findMedian(self):
        n = len(self.nums)
        if n % 2 == 1:
            return self.nums[n // 2]
        return (self.nums[n // 2 - 1] + self.nums[n // 2]) / 2

Use a max heap for the lower half and a min heap for the upper half.

CodeT: O(log n) add, O(1) find | S: O(n)
import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max heap (inverted)
        self.hi = []  # min heap
    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 -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Same two heaps approach with balanced sizes.

Diagram

addNum(1): small=[1], large=[] addNum(2): small=[1], large=[2] findMedian: (1+2)/2 = 1.5 addNum(3): small=[2,1], large=[3] findMedian: 2.0
CodeT: O(log n) add, O(1) find | S: O(n)
import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap
        self.large = []  # min heap
    def addNum(self, num):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))
    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2.0

Complexity Comparison

Sorting
T: O(n) add, O(1) findS: O(n)

Store all numbers in a sorted list. Find median by index.

Two Heaps
T: O(log n) add, O(1) findS: O(n)

Use a max heap for the lower half and a min heap for the upper half.

Optimized Two Heaps
T: O(log n) add, O(1) findS: O(n)

Same two heaps approach with balanced sizes.

Common Mistakes

Using a single sorted list (O(n) per add)

Not balancing the heap sizes correctly

Forgetting to invert values for max heap in Python

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems