Find Median from Data Stream
Part of Practice: Scheduling & Streams
Design a MedianFinder class with two methods: addNum(num) inserts a number from a stream, and findMedian() returns the median of all numbers inserted so far. The median is the middle value when the numbers are laid out in sorted order — or the average of the two middle values when the count is even.
Both methods may each be called up to 5 × 10^4 times in any interleaving, with values between -10^5 and 10^5, so both operations must be much faster than re-sorting the data.
Examples
- Input:
- addNum(1); addNum(2); findMedian(); addNum(3); findMedian()
- Output:
- 1.5, 2.0
After inserting 1 and 2 the sorted data is [1, 2], so the median is (1 + 2) / 2 = 1.5. After inserting 3 it is [1, 2, 3], with middle value 2.
- Input:
- addNum(6); findMedian(); addNum(10); findMedian(); addNum(2); findMedian()
- Output:
- 6.0, 8.0, 6.0
[6] → 6. [6, 10] → (6 + 10) / 2 = 8. [2, 6, 10] → 6.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.