LeetCode 295 ·
Hard
Find Median from Data Stream
Support addNum and findMedian over a growing stream of numbers.
Try it
Step through the core mechanic. The simulator below runs the heap shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Heap — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
Two heaps: a max-heap of the lower half and a min-heap of the upper half, kept balanced in size. The median is the top of the larger heap, or the average of both tops when sizes are equal.
| Aspect | Value |
|---|---|
| Pattern | Heap |
| Recognise it by | Running median of a stream. |
| Time complexity | O(log n) |
| Space complexity | O(n) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.