Find Median from Data Stream
Problem Description
Question
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 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
Constraints:
- -105 <= num <= 105
- There will be at least one element in the data structure before calling
findMedian. - At most 5 * 104 calls will be made to
addNumandfindMedian.
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?
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
In the brute force approach, every time we add a new number to our data structure, we will insert it into an existing list and sort it. This will allow us to easily compute the median by accessing the middle element(s) of the sorted list.
Approach:
- Use a dynamic array to store the numbers.
addNum(int num): Insert the incoming number into this array and then sort it.findMedian(): Access the middle element or the average of two middle elements to get the median.
Code:
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array.
- Space Complexity: O(n), due to the use of additional array.
2. Two Heaps Approach
Intuition:
To optimize the process, we can use two heaps:
- A max heap for the left part
- A min heap for the right part
The median can be quickly found by:
- Taking the top of one or both heaps, depending on the number of elements.
Approach:
- Maintain two heaps:
- A max heap to store the smaller half of the numbers.
- A min heap to store the larger half of the numbers.
addNum(int num):- If the new number is less than the max in max heap, add to max heap; otherwise, add to the min heap.
- Balance the heaps so they contain equal numbers, or max heap has one extra.
findMedian():- If both heaps have the same size, the median is the average of the tops of both heaps.
- If max heap has one more element, the median is its top.
Code:
Complexity Analysis
- Time Complexity: Adding a number: O(log n) due to the insertion operation in heaps. Finding median: O(1).
- Space Complexity: O(n) to store the numbers in the heaps.