Find the Running Median

Problem Design a data structure that accepts numbers from a stream one at a time and can return the median of everything added so far, at any point.

Input / Output

• Input: a sequence of addNum(x) calls interleaved with findMedian() calls.
• Output: for each findMedian(), the median of all numbers inserted so far — the middle element for an odd count, the average of the two middle elements for an even count.

Constraints

• Numbers arrive in a stream; the full input is not known in advance and may not fit in memory.
• Median must be queryable after every insertion, so re-sorting per query is far too slow.
• Values may be negative or duplicated.

Example

• add 5 -> median 5
• add 15 -> median 10 (average of 5 and 15)
• add 1 -> median 5
• add 3 -> median 4 (average of 3 and 5)
• Tricky case: an even count returns a fractional average, so the return type must be a float, not an int.