Running Median | Practice

Write a class MedianFinder that collects integers and reports their median:

addNum(num) adds num to the collection.
findMedian() returns the median of every number added so far.

The median is the middle value once the numbers are sorted. With an even count there are two middle values, and the median is their average, so the median of [2, 3] is 2.5. findMedian is only called after at least one number has been added. Aim for O(log n) per addNum and O(1) per findMedian.

Each test is a list of calls, starting with the constructor; the expected answer lists what each call returns (null for the constructor and for addNum). A median within 10⁻⁵ of the right value is accepted.

Example 1

Calls: MedianFinder(), addNum(4), addNum(10), findMedian(), addNum(6), findMedian()
Returns: [null, null, null, 7, null, 6]

After 4 and 10 the median is their average, 7. Adding 6 makes it the middle value.

Example 2

Calls: MedianFinder(), addNum(5), findMedian(), addNum(-4), addNum(10), findMedian(), addNum(0), findMedian()
Returns: [null, null, 5, null, null, 5, null, 2.5]

Sorted, the last collection is −4, 0, 5, 10, so the median is the average of 0 and 5.

Constraints

Every number is between −10⁵ and 10⁵.
A test makes at most 5 × 10⁴ calls.

Show the pattern

Heap

The median splits the numbers into a lower half and an upper half, and only the largest of the lower half and the smallest of the upper half matter. Two heaps, one per half, keep both on top.

See heap in a visualiser

Show the approach

Keep two heaps: low, a max-heap holding the smaller half of the numbers, and high, a min-heap holding the larger half. Keep every number in low no bigger than every number in high, and keep low the same size as high or one bigger.

To add a number, push it into low, then move low's largest into high; that keeps the halves in order whichever half the number belongs to. If high is now bigger than low, move its smallest back. The median is the top of low when the count is odd, and the average of the two tops when it is even.

Time: O(log n) per addNum, O(1) per findMedian · Space: O(n)

Brush up firstHeap visualiser