Number Stream Median

You're building a running statistic over a stream of numbers. Numbers arrive one at a time, and after every arrival a downstream consumer may ask for the current median — the middle value of everything you've seen so far. You can't re-process history on each query because the stream may have ingested millions of numbers; you need ingestion in O(log n) and the median itself in O(1).

Implement a class MedianFinder with two instance methods. addNum(num) ingests one number and returns nothing. findMedian() returns the current median, computed from every number ingested so far. Both methods get called arbitrarily often and in any order.

Signature

class MedianFinder {
  addNum(num: number): void;     // O(log n) per call
  findMedian(): number | undefined; // O(1) per call
}

The median of an odd-sized set is the middle value. The median of an even-sized set is the average of the two middle values. Before any number has been ingested, findMedian() returns undefined.

Examples

const m = new MedianFinder();

m.addNum(1);
m.findMedian(); // 1     — single number is its own median

m.addNum(2);
m.findMedian(); // 1.5   — average of 1 and 2

m.addNum(3);
m.findMedian(); // 2     — middle of 1, 2, 3

m.addNum(4);
m.findMedian(); // 2.5   — average of 2 and 3

m.addNum(5);
m.findMedian(); // 3     — middle of 1, 2, 3, 4, 5

Insertion order does not change the median — these arrive 5, 4, 3, 2, 1 and produce the exact same sequence:

const m = new MedianFinder();
[5, 4, 3, 2, 1].forEach((n) => m.addNum(n));
// after each addNum, findMedian() returns: 5, 4.5, 4, 3.5, 3
// final findMedian() === 3

Calling findMedian() repeatedly without an intervening addNum returns the same value:

const m = new MedianFinder();
m.addNum(7);
m.addNum(2);
m.findMedian(); // 4.5
m.findMedian(); // 4.5  — no mutation

Notes

• Per-call complexity is the constraint. addNum must be O(log n) and findMedian must be O(1). A sorted array (insert by splice) and an unsorted bag (sort on query) both meet correctness but fail the bound — see the solution for why.
• Even count returns the float average. For addNum(1); addNum(2), findMedian() is 1.5, not 1 or 2. JavaScript's / does the right thing on numbers.
• Empty finder. findMedian() on a fresh instance returns undefined. (Throwing is an acceptable alternative if you prefer; the tests here expect undefined.)
• Each instance is independent. Two new MedianFinder() instances share no state.
• Don't expose internals. Whatever data structure you pick to hold the stream is an implementation detail. Tests treat the instance as a black box.
• Numbers, not just integers. Floats, negatives, and duplicates all flow through; the median definition is unchanged.