Find Median from Data Stream
Design a structure with addNum(num) and findMedian(). (In the playground, a stream of numbers is added one by one and the median is recorded after each.)
A way to picture it
Picture a seesaw. The left seat is a pile of the smaller numbers with its biggest on top; the right seat is a pile of the bigger numbers with its smallest on top. Keep the seesaw balanced, and the median is always sitting right at the middle, on the two tops.
How to approach it
A max-heap holds the smaller half and a min-heap holds the larger half, with sizes differing by at most one. The median comes from the tops.
Example
Input: {"stream":[1,2,3]}. Output: [1,1.5,2].
Complexity: O(log n) add, O(1) median time and O(n) space. Each add does a constant number of heap operations.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.