Hard · Two Heaps
Understand → Visualise → Practice.
After each inserted integer, return the median of all values seen; for an even count use floor of the two middle values' average.
Keep the smaller half in a max-heap and the larger half in a min-heap, balanced so their sizes differ by at most one. The median comes from their tops.
Push into the max-heap of the lower half, then move its top to the upper half to keep the halves ordered.
If the upper half becomes bigger, move its top back, so the lower half has the extra element.
Odd count: the lower half's top. Even: ⌊(lower top + upper top) / 2⌋.
O(log n) per insertion and O(n) space.
Use floor division for the even case; in some languages integer division of a negative sum rounds towards zero instead of down.
Read the full guide first: Heaps and Priority Queues.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.