Watch 10 video solutions for Find Median from Data Stream, a hard level problem involving Two Pointers, Design, Sorting. This walkthrough by NeetCode has 219,763 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
arr = [2,3,4], the median is 3.arr = [2,3], the median is (2 + 3) / 2 = 2.5.Implement the MedianFinder class:
MedianFinder() initializes the MedianFinder object.void addNum(int num) adds the integer num from the data stream to the data structure.double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
Constraints:
-105 <= num <= 105findMedian.5 * 104 calls will be made to addNum and findMedian.
Follow up:
[0, 100], how would you optimize your solution?99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?Problem Overview: Design a data structure that continuously receives numbers from a stream and returns the median at any moment. After each insertion, you must efficiently compute the middle value of all elements seen so far.
Approach 1: Two Heaps (Min-Heap + Max-Heap) (Insertion: O(log n), Median: O(1))
The optimal solution maintains two heaps that split the dataset into two halves. A max-heap stores the smaller half of numbers, while a min-heap stores the larger half. This ensures the largest value of the left half and the smallest value of the right half are always accessible. When inserting a number, push it into one heap and rebalance so the size difference never exceeds one. If both heaps have equal size, the median is the average of their top elements; otherwise it is the top of the larger heap. Heap insertions and rebalancing cost O(log n), while retrieving the median is O(1). This technique heavily relies on Heap (Priority Queue) operations and is commonly used in design problems involving streaming data.
Approach 2: Balanced Binary Search Tree (Insertion: O(log n), Median: O(1) or O(log n))
A balanced binary search tree keeps elements sorted as they arrive. Each insertion takes O(log n) because the tree maintains ordering automatically. To retrieve the median efficiently, track pointers (or iterators) to the middle element(s) and update them whenever a new value is inserted. When the number of elements becomes even, the median is the average of the two center values; when odd, it is the middle node. This approach leverages ordered traversal properties of a balanced BST and relates closely to sorting behavior, since the structure always maintains sorted order. Space complexity is O(n) because all numbers must remain stored.
Recommended for interviews: The two-heap strategy is the expected solution. It demonstrates understanding of heap balancing, streaming data handling, and efficient median queries. Discussing the BST approach shows awareness of ordered data structures, but the heap-based design is more common in production systems and coding interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Heaps (Min-Heap + Max-Heap) | addNum: O(log n), findMedian: O(1) | O(n) | Best general solution for streaming numbers and interview scenarios |
| Balanced Binary Search Tree | addNum: O(log n), findMedian: O(1)-O(log n) | O(n) | Useful when an ordered structure or iterator access is already required |