Blind 75 Visualized

#28 · Heap / Priority Queue

Find Median from Data Stream

Design a data structure that supports addNum(num), which inserts an integer from a data stream, and findMedian(), which returns the median of everything inserted so far.

HardLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Two heaps (max-heap + min-heap)

Split the sorted stream in two halves. The lower half sits in a max-heap, so its top is the largest of the small numbers; the upper half sits in a min-heap, so its top is the smallest of the large numbers. The median is built from those two tops only.

Memory layout

Two array-backed binary heaps. O(n) memory in total; each keeps only the elements of its half, in partial heap order, never fully sorted.

OperationCost
addNumO(log n)
findMedianO(1)
spaceO(n)

Balance invariant

Keep size(low) equal to size(high), or one larger. Then the median is low.top when the count is odd, and the average of the two tops when it is even. All the work of the structure is maintaining that invariant after every insert.

Memory layout

Just two integers (the sizes), implicit in the heaps.

OperationCost
rebalanceat most one move: O(log n)

Why it fits

  • The median depends only on the largest value of the lower half and the smallest value of the upper half. A heap exposes exactly its extreme in O(1), and updates it in O(log n).
  • A fully sorted structure would answer more than needed: we never ask for the k-th smallest, only the middle.
  • Because every insert changes each half by at most one element, one move between the heaps always restores balance.

Why alternatives degrade

Sort on every query:
O(n log n) per findMedian: far too slow when queries are frequent.
Sorted array with binary-search insertion:
findMedian is O(1) but every insert shifts up to n elements: O(n) per addNum.
Balanced BST / order-statistic tree:
Gives O(log n) for both operations, but needs a rank-aware self-balancing tree that is complex to write and has worse constants than two heaps.

Four approaches, from naive to production

1 · beginner

Plain list, sort on query

time addNum O(1), findMedian O(n log n)space O(n)

Append every number to a list. On findMedian, sort the list and read the middle element (or average the two middle elements).

class MedianFinder {
    vector<int> nums;
public:
    void addNum(int num) {
        nums.push_back(num);
    }
    double findMedian() {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int mid = n >> 1;
        if (n % 2 == 1) return nums[mid];
        return ((double)nums[mid - 1] + nums[mid]) / 2;
    }
};

Flaws & bottlenecks

  • Re-sorts the whole list at every query, even when only one number was added since the last one.
  • Quadratic behavior for interleaved add/query workloads: n queries cost O(n² log n).
  • Never uses the fact that the previous sort is still almost correct.

Interviewer cross-questions

What if the queries are rare?

Say: Then this is perfectly fine: O(1) insertion and one sort when it matters. The cost only explodes when queries are as frequent as inserts.

How could you avoid re-sorting?

Say: Keep the list sorted by inserting each number in its place (binary search finds the position), so every query is O(1).

Is the sort stable or relevant?

Say: Stability is irrelevant for numbers. Note that after the first sort the list is mostly sorted, which adaptive sorts (like Timsort) exploit, but it is still not better than O(n) per query.

2 · intermediate

Sorted list, binary-search insertion

time addNum O(n), findMedian O(1)space O(n)

Keep the list sorted at all times: binary-search the insertion position for each new number and insert it there. The median is then read in O(1).

class MedianFinder {
    vector<int> nums;
public:
    void addNum(int num) {
        int lo = 0;
        int hi = nums.size();
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (nums[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        nums.insert(nums.begin() + lo, num);
    }
    double findMedian() {
        int n = nums.size();
        int mid = n >> 1;
        if (n % 2 == 1) return nums[mid];
        return ((double)nums[mid - 1] + nums[mid]) / 2;
    }
};

Flaws & bottlenecks

  • Insertion into an array shifts up to n elements: O(n) per addNum even though the position was found in O(log n).
  • Each insert moves memory (cheap in practice for small n, costly for millions).
  • Better than sorting on every query, but still linear per insert.

Interviewer cross-questions

Why is the insertion O(n) even with binary search?

Say: Binary search finds the position in O(log n), but an array must move all later elements one slot to make room. A linked list inserts in O(1) but cannot be binary searched.

When is this a good choice?

Say: When n is small (a few thousand) or queries heavily outnumber inserts. The constant factor of memmove is tiny, so it often beats heaps in practice for modest n.

Can you get O(log n) for both operations?

Say: Yes: two heaps. They keep just enough order for the median: the top of each half.

3 · advanced

Two heaps

time addNum O(log n), findMedian O(1)space O(n)

A max-heap holds the smaller half and a min-heap the larger half, kept equal in size (low may have one extra). A new number goes into the correct half, then at most one element moves across to rebalance.

class MedianFinder {
    priority_queue<int> low;
    priority_queue<int, vector<int>, greater<int>> high;
public:
    void addNum(int num) {
        if (low.empty() || num <= low.top()) low.push(num);
        else high.push(num);
        if (low.size() > high.size() + 1) { high.push(low.top()); low.pop(); }
        else if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
    }
    double findMedian() {
        if (low.size() > high.size()) return low.top();
        return ((double)low.top() + high.top()) / 2;
    }
};

Flaws & bottlenecks

  • Needs two heaps (and a custom heap in JavaScript).
  • The rebalance logic has two directions to get right; a mistake leaves the sizes off by two and the median wrong.
  • Cannot answer other order statistics (for example the 90th percentile) without a different split point.

Interviewer cross-questions

Why does the median come only from the two tops?

Say: Everything in the lower heap is ≤ everything in the upper heap, and the sizes are equal (or low has one extra). So the middle element is the largest of the lower half, and for an even count the second middle is the smallest of the upper half.

What if all numbers are integers in 0..100?

Say: Use a counting array of 101 buckets: addNum is O(1) and findMedian walks at most 101 buckets, so it is constant time. If 99% of the values are in 0..100, keep the counts plus a small structure for the outliers.

How do you handle deletion or a sliding window?

Say: Heaps cannot delete arbitrary elements efficiently. Use lazy deletion (mark elements dead and discard them when they reach the top) or an order-statistic tree, as in "Sliding Window Median".

4 · expert

Push, pop, rebalance (no comparisons)

time addNum O(log n), findMedian O(1)space O(n)

Always push the new number into the lower heap, always move that heap's maximum into the upper heap, and give one element back if the upper heap grew too large. The halves stay separated without ever comparing the new number with a heap top.

class MedianFinder {
    priority_queue<int> low;
    priority_queue<int, vector<int>, greater<int>> high;
public:
    void addNum(int num) {
        low.push(num);
        high.push(low.top()); low.pop();
        if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
    }
    double findMedian() {
        return low.size() > high.size() ? low.top() : ((double)low.top() + high.top()) / 2;
    }
};

Flaws & bottlenecks

  • Always performs three heap operations per insert, even when the number already belongs where it would go (up to 3× the heap work of the compare-first version).
  • The correctness argument is subtle and easy to get wrong when modified.
  • Still stores everything: memory grows with the stream.

Interviewer cross-questions

Why is it correct to push into the lower heap blindly?

Say: After the push, the lower heap holds its old elements plus the new number. Moving its maximum to the upper heap puts the largest of the lower side into the upper side: every element left in the lower heap is ≤ that maximum, and the maximum is ≤ everything already in the upper heap only if it belongs there. Whichever number was the new maximum, the sets remain correctly partitioned; the extra rebalance restores the sizes.

Why would you prefer it to the compare-first version?

Say: It has no branch on the value, so the code is shorter and harder to get wrong: the invariant is restored by construction. The compare-first version is faster on average because it often does only one heap operation.

How would you make it faster for a very long stream?

Say: If the values come from a bounded range, replace the heaps with counting buckets. If only an approximate median is needed, use a streaming sketch (a t-digest or quantile sketch) with O(1) memory.

Synchronized code walkthrough

Showing: Plain list, sort on query — shares the player above; click any step to jump.

class MedianFinder {
    vector<int> nums;
public:
    void addNum(int num) {
        nums.push_back(num);
    }
    double findMedian() {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int mid = n >> 1;
        if (n % 2 == 1) return nums[mid];
        return ((double)nums[mid - 1] + nums[mid]) / 2;
    }
};