The Median Problem

Given a stream of numbers, find the median at any point. The median is the middle element. For odd count, it's the center.

For even count, it's the average of the two center elements. Challenge: after each insertion, you need the median in $O(1)$ time.

Sorting after each insertion is $O(n \log n)$, too slow. A clever technique uses two heaps to maintain $O(\log n)$ insertion with $O(1)$ median queries.