Find Median from Data Stream

Hard Heaps Advanced Original on LeetCode

Find Median from Data Stream is a hard heaps problem solved with the advanced pattern. The best approach, optimal (two heaps), runs in addNum O(log n), findMedian O(1) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (sort on every query) up.

Problem

Build a MedianFinder class that receives integers one at a time and can report the median of everything it has received so far.

  • addNum(num) adds the integer num to the collection.
  • findMedian() returns the median as a decimal number: the middle value when the count is odd, or the average of the two middle values when the count is even.

Examples

Example 1

Input
addNum(7), addNum(3), findMedian(), addNum(5), findMedian(), addNum(10), findMedian()
Output
5.0, 5.0, 6.0
Why
{3, 7} gives (3 + 7) / 2 = 5.0; {3, 5, 7} gives 5.0; {3, 5, 7, 10} gives (5 + 7) / 2 = 6.0.

Example 2

Input
addNum(-4), findMedian(), addNum(-4), addNum(9), findMedian()
Output
-4.0, -4.0
Why
A single value is its own median; {-4, -4, 9} has -4 in the middle.

Constraints

  • -10^5 <= num <= 10^5
  • findMedian is only called after at least one addNum.
  • At most 5 * 10^4 calls in total.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sort on every query)addNum O(1), findMedian O(n log n)O(n)
Better (keep the list sorted)addNum O(n), findMedian O(1)O(n)
Optimal (two heaps)addNum O(log n), findMedian O(1)O(n)

1Brute force (sort on every query)

TimeaddNum O(1), findMedian O(n log n)Each query sorts all n values again.
SpaceO(n)The list holds every number, plus a sorted copy during a query.

Append each number to a list. When the median is asked for, copy and sort the list and read the middle one or two values.

  1. addNum appends to the list.
  2. findMedian sorts a copy of the list.
  3. Odd size: return the middle value. Even size: return the average of the two middle values.
class MedianFinder {
    private final List<Integer> data = new ArrayList<>();

    public void addNum(int num) { data.add(num); }

    public double findMedian() {
        List<Integer> s = new ArrayList<>(data);
        Collections.sort(s);
        int n = s.size();
        if (n % 2 == 1) return s.get(n / 2);
        return (s.get(n / 2 - 1) + s.get(n / 2)) / 2.0;
    }
}

2Better (keep the list sorted)

TimeaddNum O(n), findMedian O(1)The binary search is O(log n), but inserting shifts up to n elements.
SpaceO(n)The sorted list holds every number.

Keep the list sorted at all times. Binary search for where each new number belongs and insert it there, so the median is always one index lookup away.

  1. addNum: binary search for the first position whose value is >= num, insert num there.
  2. findMedian: read the middle one or two values directly.
class MedianFinder {
    private final List<Integer> s = new ArrayList<>();

    public void addNum(int num) {
        int lo = 0, hi = s.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (s.get(mid) < num) lo = mid + 1; else hi = mid;
        }
        s.add(lo, num);
    }

    public double findMedian() {
        int n = s.size();
        if (n % 2 == 1) return s.get(n / 2);
        return (s.get(n / 2 - 1) + s.get(n / 2)) / 2.0;
    }
}

3Optimal (two heaps)

TimeaddNum O(log n), findMedian O(1)Each add does a constant number of heap pushes and pops, each O(log n).
SpaceO(n)The two heaps together hold every number.

Split the numbers into a lower half and an upper half. A max-heap holds the lower half and a min-heap holds the upper half. The lower heap is allowed one extra element. The median is then either the top of the lower heap, or the average of both tops.

  1. addNum: push num into the max-heap low, then move the top of low into the min-heap high (this keeps every value in low <= every value in high).
  2. If high is now bigger than low, move the top of high back into low.
  3. findMedian: if low is bigger, return its top; otherwise return the average of both tops.
class MedianFinder {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    private final PriorityQueue<Integer> high = new PriorityQueue<>();

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (high.size() > low.size()) low.offer(high.poll());
    }

    public double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + high.peek()) / 2.0;
    }
}

Edge cases to test

  • Only one number added so far
  • Many equal values
  • Numbers arriving in strictly increasing or strictly decreasing order
  • An even count, where the median is the average of two values and may end in .5

Hints

Hint 1

Sorting on every query works but repeats a lot of work. What do you really need to know to read the median?

Hint 2

You only need the largest value of the lower half and the smallest value of the upper half.

Hint 3

Keep the lower half in a max-heap and the upper half in a min-heap, and keep their sizes within one of each other.

FAQ

What is the best time complexity for Find Median from Data Stream?

Optimal (two heaps) runs in addNum O(log n), findMedian O(1) time and O(n) extra space. Each add does a constant number of heap pushes and pops, each O(log n).

Which pattern does Find Median from Data Stream use?

It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Trapping Rain Water II, Minimum Number of Refueling Stops.

Is there a brute force solution for Find Median from Data Stream?

Yes. Brute force (sort on every query) takes addNum O(1), findMedian O(n log n) time and O(n) space. Append each number to a list.

Which edge cases should I test for Find Median from Data Stream?

Only one number added so far; Many equal values; Numbers arriving in strictly increasing or strictly decreasing order; An even count, where the median is the average of two values and may end in .5.