Find Median from Data Stream - Video Solutions
Find Median from Data Stream - Heap & Priority Queue - Leetcode 295
Find Median from Data Stream - Video Solution
Watch 10 video solutions for Find Median from Data Stream, a hard level problem involving Two Pointers, Design, Sorting. This walkthrough by NeetCode has 286,142 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
- For example, for
arr = [2,3,4], the median is3. - For example, for
arr = [2,3], the median is(2 + 3) / 2 = 2.5.
Implement the MedianFinder class:
MedianFinder()initializes theMedianFinderobject.void addNum(int num)adds the integernumfrom the data stream to the data structure.double findMedian()returns the median of all elements so far. Answers within10-5of 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 <= 105- There will be at least one element in the data structure before calling
findMedian. - At most
5 * 104calls will be made toaddNumandfindMedian.
Follow up:
- If all integer numbers from the stream are in the range
[0, 100], how would you optimize your solution? - If
99%of all integer numbers from the stream are in the range[0, 100], how would you optimize your solution?
Approach Overview
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.
Complexity Analysis
| 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 |