Find Median from Data Stream

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Numbers arrive one at a time. After any of them, you may be asked for the median of everything seen so far. Implement addNum(num) and findMedian(). With an odd count the median is the middle value; with an even count it is the average of the two middle values.

    A short question with a classic answer: two heaps that split the data in half. It shows up as "running median of latencies" or "median price so far", and it is the base for Sliding Window Median. Original problem: LeetCode 295.

    Example

    After each new number, the median is the middle of the sorted values so far (green), or the average of the two middles.
    After each new number, the median is the middle of the sorted values so far (green), or the average of the two middles.
    addNum(5)   findMedian() -> 5
    addNum(15)  findMedian() -> 10.0     # (5 + 15) / 2
    addNum(1)   findMedian() -> 5
    addNum(3)   findMedian() -> 4.0      # (3 + 5) / 2
    addNum(8)   findMedian() -> 5

    Constraints (assumed)

    • Up to 5 × 10⁴ calls in total; values fit in a 32-bit int.
    • findMedian is only called after at least one addNum.

    What this question tests

    • Seeing that you only need the middle, not the whole sorted order.
    • Keeping two heaps with two invariants: order between them, and sizes within one of each other.
    • Handling the even case without integer-division mistakes.

    Questions to ask first

    1. How often is each method called? Mostly adds, mostly reads, or balanced?
    2. What range do the numbers have? A small fixed range allows counting instead of heaps.
    3. Return type for the even case? (Here: a float, the exact average.)
    4. Will numbers ever be removed? (Here: no. With removals this becomes Sliding Window Median.)