hardHeap / Priority Queue

Find Median from Data Stream

After each incoming integer, report the median of all values received so far.

LeetCode ↗

Work through the cases

3 examples

Input notation

Incoming integers separated by spaces.

Expected result

One median per line, with one decimal place.

Case 1

Input

4 2 8

Expected output

4.0
3.0
4.0

Case 2

Input

-1 1

Expected output

-1.0
0.0

Case 3

Input

0 0

Expected output

0.0
0.0

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Sorting after every insertion is too slow for a running median. A max-heap holds the lower half and a min-heap the upper half; the tops form the median. A new value goes into the max-heap then is moved to the min-heap, keeping the min-heap at most one larger. Even counts average the two tops; odd counts take the min-heap top.

We can use two heaps to maintain all the elements, a min heap minQ and a max heap maxQ, where the min heap minQ stores the larger half, and the max heap maxQ stores the smaller half.

When calling the addNum method, we first add the element to the max heap maxQ, then pop the top element of maxQ and add it to the min heap minQ. If at this time the size difference between minQ and maxQ is greater than 1, we pop the top element of minQ and add it to maxQ. The time complexity is O(log n).

When calling the findMedian method, if the size of minQ is equal to the size of maxQ, it means the total number of elements is even, and we can return the average value of the top elements of minQ and maxQ; otherwise, we return the top element of minQ. The time complexity is O(1).

The space complexity is O(n), where n is the number of elements.

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

    public MedianFinder() {
    }

    public void addNum(int num) {
        maxQ.offer(num);
        minQ.offer(maxQ.poll());
        if (minQ.size() - maxQ.size() > 1) {
            maxQ.offer(minQ.poll());
        }
    }

    public double findMedian() {
        return minQ.size() == maxQ.size() ? (minQ.peek() + maxQ.peek()) / 2.0 : minQ.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.