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.
The main idea is to use a max-heap to store the smaller half of the numbers and a min-heap to store the larger half. The max-heap allows you to efficiently fetch the largest element of the smaller half, and the min-heap allows you to efficiently fetch the smallest element of the larger half. To maintain the balance, ensure that the number of elements in the max-heap is either equal to or one more than the number of elements in the min-heap.
The solution uses two heaps (small and large). 'small' is a max-heap that stores the smaller half of the numbers, and 'large' is a min-heap that stores the larger half. Each time a number is added, it is pushed to the max-heap first. If the max-heap's largest is greater than the min-heap's smallest, balance them by moving numbers between heaps. The median can be derived based on the sizes of the heaps.
C++
Java
JavaScript
The time complexity for adding a number is O(log n) due to heap adjustments. Finding the median has a time complexity of O(1). Space complexity is O(n), where n is the number of elements.
An alternative approach is to use a balanced binary search tree (BST) to keep track of the numbers. This allows maintaining a sorted order of elements, which can make finding the median efficient since a BST can give average-case time complexity of O(log n) for insertion and O(1) for median finding.
This C# implementation uses two sorted sets as a stand-in for a balanced BST. Every number is inserted into the smaller set first, followed by balancing between the two sets. The median is retrieved based on the sizes of the sets and their boundary values.
Insertion and balancing in the sorted set take O(log n) time, and findings of the median are O(1). Space complexity is O(n).
| Approach | Complexity |
|---|---|
| Using Two Heaps (Min-Heap and Max-Heap) | The time complexity for adding a number is O(log n) due to heap adjustments. Finding the median has a time complexity of O(1). Space complexity is O(n), where n is the number of elements. |
| Using a Balanced Binary Search Tree | Insertion and balancing in the sorted set take O(log n) time, and findings of the median are O(1). Space complexity is O(n). |
| 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 |
Find Median from Data Stream - Heap & Priority Queue - Leetcode 295 • NeetCode • 219,763 views views
Watch 9 more video solutions →Practice Find Median from Data Stream with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor