Back to solutions

Find Median from Data Stream

HardHeaps

Design a structure that adds numbers from a stream and can return the median of all numbers so far.

Open problem
Constraints
  • -10^5 <= num <= 10^5
  • Up to 5 * 10^4 calls

Two balanced heaps

Time O(log n) per add, O(1) for medianSpace O(n)

A max-heap holds the smaller half and a min-heap the larger half, kept balanced in size. The median is the top of the larger heap, or the average of both tops when sizes are equal.

#include <bits/stdc++.h>
using namespace std;

class MedianFinder {
    priority_queue<int> lo; // max-heap, smaller half
    priority_queue<int, vector<int>, greater<int>> hi; // min-heap, larger half
public:
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top()); lo.pop();
        if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double findMedian() {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};