Back to DSA

Find Median from Data Stream

hard
Acceptance: 39%
HeapDesignTwo Pointers

Design a data structure that accepts a continuous stream of integers and can report the median at any time. If the count of numbers is even, the median is the average of the two middle values.

Examples

Example 1:
Input:MedianFinder(), addNum(5), addNum(3), findMedian(), addNum(8), findMedian()
Output:[null,null,null,4.0,null,5.0]

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyValid PalindromeeasyMerge Sorted ArrayeasyMove ZeroeseasyContainer With Most Watermedium
00:00
import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> hi = new PriorityQueue<>();

    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (lo.size() < hi.size()) lo.offer(hi.poll());
    }

    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}
Time complexityO(log n)
Space complexityO(n)