LeetEye LeetEye
Hard Heap / Priority Queue ~5 min

Find Median from Data Stream

heap find-median-from-data-stream

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:
- MedianFinder() initializes the MedianFinder object.
- void addNum(int num) adds the integer num from the data stream to the data structure.
- double findMedian() returns the median of all elements so far.

Examples

Example 1
Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
Output: [null, null, null, 1.5, null, 2.0]
Key Insight

Use two heaps: max-heap for smaller half, min-heap for larger half.

Two heaps: max-heap for smaller half, min-heap for larger half. Keep balanced (sizes differ <= 1). Median = top of larger heap or average of tops.

How to Approach This Problem

Pattern Recognition: When you see keywords like find median from data stream heap, think Heap / Priority Queue.

Step-by-Step Reasoning

1 Using a sorted list for each insert:
Answer: O(n) insert, O(1) find median
Inserting into sorted list is O(n). We want O(log n) insert.
2 For the smaller half, we use:
Answer: Max-heap
We need quick access to the LARGEST of the smaller half. Max-heap gives max at root.
3 For the larger half, we use:
Answer: Min-heap
We need quick access to the SMALLEST of the larger half. Min-heap gives min at root.
4 The heaps should be balanced such that:
Answer: Sizes differ by at most 1
For odd count, one heap has one extra element (median is its top). For even, both same size.
5 If total count is odd, median is:
Answer: Top of the heap with more elements
The extra element is the median. Whichever heap has n/2+1 elements has the median.
6 If total count is even, median is:
Answer: Average of both tops
Two middle elements are at the boundary. Average them.

Solution

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # Max-heap (negated values)
        self.large = []  # Min-heap
    
    def addNum(self, num: int) -> None:
        # Add to max-heap (smaller half)
        heapq.heappush(self.small, -num)
        
        # Balance: move largest from small to large
        heapq.heappush(self.large, -heapq.heappop(self.small))
        
        # Ensure small has >= elements as large
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))
    
    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

Complexity Analysis

Time O(log n) add, O(1) find
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Heap / Priority Queue problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye