Why sorting is the wrong instinct#
Numbers arrive one at a time and after each one you have to report the median. Sorting the whole collection each time is O(n log n) per query. Inserting into a sorted array is O(n) per insert because of the shifting. With 100000 operations, neither survives.
What you actually need is much less than a sorted list. You need the middle, and nothing else.
The arrangement#
Split the values into two halves:
- A max heap holding the smaller half. Its top is the largest of the small values.
- A min heap holding the larger half. Its top is the smallest of the large values.
Those two tops sit either side of the median. If the halves are the same size, the median is their average. If one half has one extra element, its top is the median.
Insert in three steps#
- Push onto one heap. A simple rule: if the value is less than or equal to the top of the max heap, it belongs in the small half, otherwise the large half.
- Rebalance so the sizes differ by at most one. If one side got two ahead, move its top across.
- The median is now readable from the tops.
Each step is O(log n), and reading the median is O(1).
The invariant to protect#
Every value in the max heap must be less than or equal to every value in the min heap. If that ever breaks, the tops stop being the middle and the answers go quietly wrong rather than crashing.
A shortcut that keeps it true without any thinking: always push onto the max heap first, move its top to the min heap, and then, if the min heap is now larger, move its top back. Three operations, no case analysis, invariant preserved.
Watch the arithmetic#
With two large integers, (a + b) / 2 can overflow and integer division silently truncates. The median of 3 and 4 is 3.5, not 3. Use floating point for the average, or a + (b - a) / 2.0.
Where this shows up#
Sliding window medians, the IPO problem, scheduling with two priorities, and anything where you need the top of one group and the bottom of another at the same time. The general lesson: if you only need an extreme, do not maintain an order.