Integers arrive one at a time, and at any point you may be asked for the median of every integer that has arrived so far. Implement the MedianFinder class:
MedianFinder() starts with no integers.addNum(num) records the integer num.findMedian() returns the median of all the integers recorded so far.The median is the middle value once the integers are lined up in sorted order. When there is an even number of them there are two middle values, and the median is their average, so it can end in .5. An answer within 10⁻⁵ of the true median is accepted.
Sorting everything again on each findMedian is too slow at these sizes. Aim for O(log n) per addNum and O(1) per findMedian.
Each example lists the calls in order, then the arguments of each call, then what each call returns: null for the constructor and for addNum, which returns nothing.
Example 1
Input:
["MedianFinder", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
[[], [7], [], [3], [], [10], []]
Output: [null, null, 7.00000, null, 5.00000, null, 7.00000]
With only 7 recorded, the median is 7. Adding 3 gives [3, 7], whose two middle values average to 5. Adding 10 gives [3, 7, 10], and the middle value is 7 again.
Example 2
Input:
["MedianFinder", "addNum", "addNum", "addNum", "addNum", "findMedian"]
[[], [-4], [9], [-1], [2], []]
Output: [null, null, null, null, null, 0.50000]
The integers arrive out of order. Sorted, they are [-4, -1, 2, 9], and the median is (-1 + 2) / 2 = 0.5.
Example 3
Input:
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
[[], [6], [6], [], [1], [], [0], []]
Output: [null, null, null, 6.00000, null, 6.00000, null, 3.50000]
Repeated values count separately. [1, 6, 6] has median 6, and [0, 1, 6, 6] has median (1 + 6) / 2 = 3.5.
Constraints
-10⁵ <= num <= 10⁵findMedian is only called after at least one addNum.5 * 10⁴ calls are made in total to addNum and findMedian.10⁻⁵ of the true median is accepted.You never need the numbers fully sorted, only the one or two in the middle. Split them into a smaller half and a larger half; the median sits on the boundary between them.
To find a median you line the numbers up and look at the middle. But findMedian doesn't need the whole line. It needs one number, or two: the largest of the smaller half and the smallest of the larger half. Everything else only has to be on the right side of that middle, in any order.
Time O(log n) per add, O(1) per querySpace O(n)
The full walkthrough and code are part of Premium
["MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian"] [[],[7],[],[3],[],[10],[]]
[null,null,7,null,5,null,7]