295. Find median from Data Stream Leetcode Solution
Find median from Data Stream Leetcode Problem :
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 is 3.
For example, for 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.
[[], [1], [2], [], [3], []]
Find Median from Data Stream Leetcode Solution :
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 addNum and findMedian.
Intuition :
We can store the current data stream within two multisets: one containing the lower values of the stream and the other containing the upper values. If we ensure that the size of the lower set is always greater than or equal to the size of the upper set, then the largest element in the lower set will be the median.
In odd windows, the size of the lower set will be one larger than the upper set, therefore its largest element will be the median.
In even windows, the problem calls for the average of the two centermost values so we take the largest element in the lower set and smallest element in the upper set.
Approach :
For inserting, compare the incoming value to the current median and place it in the upper set if it is greater than the median, put it in the lower set otherwise. If one set fills above its max size, transfer an element to the other set. Erasing is more simple, just find the element and erase it.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class MedianFinder {
private:
multiset< int>low, up;
public:
MedianFinder() {
low.clear();
up.clear();
}
void addNum(int num) {
if(low.size()==0){
low.insert(num);
return;
}
double currentMedian=findMedian();
if(num > currentMedian){
up.insert(num);
if(up.size() > low.size()){
low.insert(*up.begin());
up.erase(up.find(*up.begin()));
}
}else{
low.insert(num);
if(low.size() - up.size() > 1){
up.insert(*low.rbegin());
low.erase(low.find(*low.rbegin()));
}
}
}
double findMedian() {
if(low.size() > up.size()){
return (double)*low.rbegin();
}else{
return ((double)(*low.rbegin() + *up.begin()))/2.0;
}
}
};
class MedianFinder {
PriorityQueue< Integer> minHeap = new PriorityQueue<>();
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
public MedianFinder() {
}
public void addNum(int num) {
if(maxHeap.size()==minHeap.size()){
minHeap.add(num);
maxHeap.add(minHeap.remove());
}
else{
maxHeap.add(num);
minHeap.add(maxHeap.remove());
}
}
public double findMedian() {
if(maxHeap.size()==minHeap.size()){
return (maxHeap.peek()+minHeap.peek())/2.0;
}
return maxHeap.peek()/1.0;
}
}
from sortedcontainers import SortedList
class MedianFinder:
def __init__(self):
self.s = SortedList()
def addNum(self, num: int) -> None:
self.s.add(num)
def findMedian(self) -> float:
l = len(self.s)
if l%2==0:
return (self.s[l//2-1]+self.s[l//2])/2
return self.s[l//2]Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment