Find Median from Data Stream
Maintain a data structure that returns the median after each insertion.
Pattern fit
The median lives between the lower half and the upper half, which is why a max heap plus min heap is the canonical design.
Key observation
One heap stores the lower half, the other stores the upper half, and their sizes differ by at most one.
Target complexity
O(log n) / O(n)
How to break down the solution cleanly
The median lives between the lower half and the upper half, which is why a max heap plus min heap is the canonical design.
One heap stores the lower half, the other stores the upper half, and their sizes differ by at most one.
Define what the heap top represents in one sentence.
Push new candidates as soon as they become eligible.
Reference implementation
Python# Generic pattern template
import heapq
heap = []
heapq.heappush(heap, value)
smallest = heapq.heappop(heap)
# max heap in Python
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
Common pitfalls
Not rebalancing after insertion.
Forgetting which heap should own the extra element when count is odd.
Common follow-ups
What invariant must always hold between the two heaps?
Why is sorting the entire stream after each insert too expensive?
Continue with related problems
Build repeatable depth inside the Heap / Priority Queue cluster before moving on.