HardTwo PointersDesignSortingHeap (Priority Queue)Data Stream

Find Median from Data Stream

1 approach, code in every language

Design a data structure that supports adding integers from a data stream and querying the median of all values received so far.

The median is the middle value of an ordered list. When the count of values is odd it is the single middle element; when the count is even it is the average of the two middle elements.

Implement the class:

- `MedianFinder()` initializes the structure. - `addNum(num)` ingests the next integer from the stream. - `findMedian()` returns the median of every value added so far as a floating-point number.

Example 1

Input: ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]

Output: [null, null, null, 1.5, null, 2.0]

After adding 1 and 2 the median is (1 + 2) / 2 = 1.5. After adding 3 the sorted values are [1, 2, 3], so the median is 2.0.

Example 2

Input: ["MedianFinder","addNum","findMedian","addNum","findMedian"] [[],[5],[],[10],[]]

Output: [null, null, 5.0, null, 7.5]

With only 5 present the median is 5.0; after adding 10 the median is (5 + 10) / 2 = 7.5.

Constraints

-10^5 <= num <= 10^5
There is at least one element before findMedian is called.
At most 5 * 10^4 calls are made to addNum and findMedian.

Two balanced heaps

Split the stream into a max-heap holding the smaller half and a min-heap holding the larger half, kept balanced so the median is always at the tops.

Loading animation…

Intuition

The median only depends on the one or two values in the middle of the sorted order, so we never need the whole sequence sorted — we just need fast access to the middle. We keep the smaller half of the numbers in a max-heap whose root is the largest of the small values, and the larger half in a min-heap whose root is the smallest of the large values. If we keep the two halves balanced in size, those two roots straddle the median. When the total count is odd we let one heap hold the extra element and its root is the median; when it is even the median is the average of the two roots. Rebalancing after every insertion keeps both heaps within one element of each other.

Algorithm walkthrough

1Maintain a max-heap `lower` for the smaller half and a min-heap `upper` for the larger half.
2To add a number, first push it onto `lower`, then move `lower`'s root over to `upper` so every value in `lower` is <= every value in `upper`.
3If `upper` now has more elements than `lower`, move `upper`'s root back to `lower` to restore balance.
4This keeps the size difference at most one, with any extra element resting in `lower`.
5For findMedian, if `lower` is larger, return its root; the total count is odd and that root is the middle value.
6Otherwise the counts are equal, so return the average of `lower`'s root and `upper`'s root.

Implementation

import heapq

class MedianFinder:
    def __init__(self):
        self.lower = []  # max-heap (store negatives)
        self.upper = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lower, -num)
        heapq.heappush(self.upper, -heapq.heappop(self.lower))
        if len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

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

Time

O(log n) per addNum, O(1) per findMedian

Space

O(n)

Each insertion performs a constant number of heap pushes/pops, each O(log n). Storing all n values costs O(n).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free