66 / 75
Hard
Find Median from Data Stream
#66heapdesigntwo-pointersdata-stream
Use two heaps: max-heap for smaller half, min-heap for larger half, balance sizes for O(1) median.
Example:
Input:
addNum(1), addNum(2), findMedian(), addNum(3), findMedian()Output:
[null, null, 1.5, null, 2.0]Common Mistakes:
- Not maintaining heap size balance (max-heap size should be equal or one more)
- Wrong heap types (max-heap for left, min-heap for right)
- Integer division instead of double for even-sized median
- Always adding to same heap first (should add to max-heap then transfer)
Notes:
Classic two-heap pattern. addNum: O(log n), findMedian: O(1). Space O(n). Keep left half in max-heap, right half in min-heap.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Use two heaps: max-heap for smaller half, min-heap for larger half, balance sizes for O(1) median.
Example:
Input:
addNum(1), addNum(2), findMedian(), addNum(3), findMedian()Output:
[null, null, 1.5, null, 2.0]Common Mistakes:
- Not maintaining heap size balance (max-heap size should be equal or one more)
- Wrong heap types (max-heap for left, min-heap for right)
- Integer division instead of double for even-sized median
- Always adding to same heap first (should add to max-heap then transfer)
Notes:
Classic two-heap pattern. addNum: O(log n), findMedian: O(1). Space O(n). Keep left half in max-heap, right half in min-heap.
66/75
Find Median from Data Stream