The median is used to describe the central tendency of a dataset. In finding the median from the data stream problem we have to implement a class, MedianFinder, to dynamically compute the median of a data stream, handling even and odd list sizes accurately. In this article, we will discuss an approach to solve this problem efficiently to find median and also discuss the time and space complexity of this problem.
Find Median from the Data Stream Problem
In this problem to find median from the data stream, we have to write a Median finder class that manages an ordered integer list, The median, the middle value of the list, is calculated differently for lists with even or odd sizes
In this problem, integers are added dynamically to a list of integers, and different functions are used to insert numbers into the list a function to find the median from the list of the current list of integers.
There are two cases:
Even: if the size of the list is even then there is no middle value, and the median is the mean of the two middle classes.
Odd: if the size of the list is odd then the middle value is the median for the current list of integers.
We have to implement the following things to solve this problem:
- MedianFinder(): initializes the MedianFinder object.
- 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.
Find Median using Heap
In this method, we divide our numbers into two groups: low numbers and high numbers. We want to quickly find the middle value (the median) without having to sort all the numbers.
- Firstly, we divide the numbers into two halves: one holds low numbers, and the other holds high numbers. To quickly access the median in constant time, we use maxHeap and minHeap to get the maximum of the low half and the minimum of the high half, respectively.
- We will use maxHeap to store half of the low numbers, the top of the maxHeap is the highest number among low numbers, minHeap to store half of the high numbers, top of the minHeap is the lowest number among high numbers.
- We have to balance the size between maxHeap and minHeap while processing. Hence after adding k elements,
- If k = 2 * i then maxHeap.size = minHeap.size = i
- If k = 2 * i + 1, let maxHeap store 1 element more than minHeap, then maxHeap.size = minHeap.size + 1.
- When we add a new number to our MedianFinder:
- First, we add the number to the maxHeap. This might result in the maxHeap containing a larger number than should be in the minHeap. To correct this, we remove the highest element from the maxHeap and add it to the minHeap.
- Next, if the minHeap has more elements than the maxHeap, we balance the sizes by removing the lowest element from the minHeap and adding it back to the maxHeap.
- When doing findMedian():
- If maxHeap.size > minHeap.size returns to the top of the maxHeap, which is the highest number among low numbers.
- Else if maxHeap.size == minHeap return the (maxHeap.top() + minHeap.top()) / 2.
C++ Code
Here is the C++ implementation of this solution:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class MedianFinder {
public:
priority_queue<int> maxHeap; // Max heap to store smaller half of numbers
priority_queue<int, vector<int>, greater<int>> minHeap; // Min heap to store larger half of numbers
MedianFinder() {
}
void addNum(int num) {
maxHeap.push(num); // Add the number to maxHeap
// Move the top element of maxHeap to minHeap
minHeap.push(maxHeap.top());
maxHeap.pop();
// If the minHeap has more elements, balance the heaps
if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if (maxHeap.size() > minHeap.size())
return maxHeap.top(); // If maxHeap has more elements, median is at the top of maxHeap
return (maxHeap.top() + minHeap.top()) / 2.0; // Otherwise, average the tops of both heaps for the median
}
};
int main() {
MedianFinder obj;
obj.addNum(1);
obj.addNum(2);
cout << obj.findMedian() << endl; // Output: 1.5
obj.addNum(3);
cout << obj.findMedian() << endl; // Output: 2.0
return 0;
}Python Code
We can do in Python programming also to find median:
import heapq
class MedianFinder:
def __init__(self):
self.maxHeap = [] # Max heap to store smaller half of numbers
self.minHeap = [] # Min heap to store larger half of numbers
def addNum(self, num):
heapq.heappush(self.maxHeap, -num) # Add the number to maxHeap
# Move the top element of maxHeap to minHeap
heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))
# If the minHeap has more elements, balance the heaps
if len(self.minHeap) > len(self.maxHeap):
heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))
def findMedian(self):
if len(self.maxHeap) > len(self.minHeap):
return -self.maxHeap[0] # If maxHeap has more elements, median is at the top of maxHeap
return (-self.maxHeap[0] + self.minHeap[0]) / 2.0 # Otherwise, average the tops of both heaps for the median
# Example Usage
obj = MedianFinder()
obj.addNum(1)
obj.addNum(2)
print(obj.findMedian()) # Output: 1.5
obj.addNum(3)
print(obj.findMedian()) # Output: 2.0Java Code
Well, let’s also solve it with Java:
import java.util.PriorityQueue;
class MedianFinder {
PriorityQueue<Integer> maxHeap; // Max heap to store smaller half of numbers
PriorityQueue<Integer> minHeap; // Min heap to store larger half of numbers
MedianFinder() {
maxHeap = new PriorityQueue<>((a, b) -> b - a);
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
maxHeap.offer(num); // Add the number to maxHeap
// Move the top element of maxHeap to minHeap
minHeap.offer(maxHeap.poll());
// If the minHeap has more elements, balance the heaps
if (minHeap.size() > maxHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() > minHeap.size())
return maxHeap.peek(); // If maxHeap has more elements, median is at the top of maxHeap
return (maxHeap.peek() + minHeap.peek()) / 2.0; // Otherwise, average the tops of both heaps for the median
}
public static void main(String[] args) {
MedianFinder obj = new MedianFinder();
obj.addNum(1);
obj.addNum(2);
System.out.println(obj.findMedian()); // Output: 1.5
obj.addNum(3);
System.out.println(obj.findMedian()); // Output: 2.0
}
}Output:
1.5
2Complexity Analysis
The Time complexity is O(log n) for adding a number and O(1) time complexity for finding the median in a data stream, where n is the number of elements added. Overall time complexity is dominated by adding numbers. The space complexity of maintaining these priority queues is O(n), where n is the number of elements added to the MedianFinder.
Conclusion
In conclusion, we have discussed the find median in the data stream problem from leetcode and we solved it using heaps and discussed how functions can be implemented using heaps and also discussed implementation in C++, Java, and Python. With time and space complexity
