hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Find Median from Data Stream
Problem: 295. Find Median from Data Stream
Problem Link:
Companies Asked: Samsung, Amazon, Google, Apple, Bloomberg, Microsoft, IXL, ServiceNow, Uber, Intuit, Facebook, Indeed, LinkedIn, Spotify, Walmart Global Tech, VMware, Citadel, Nvidia, Paypal, Zoom, ByteDance, Twitter, Goldman Sachs, Adobe, eBay, Airbnb, Oracle, Salesforce, Expedia, Akuna Capital, Twilio, DoorDash, TikTok, DE Shaw India.
Approach:
The intuition behind having the mid element of an odd-sized array or the average of two mid elements of an even-sized array where the data is continuously incoming is to use two Heap.
One of the heaps is a MinHeap and the other is a Maxheap.
Both the heap will contain N/2 elements at most.
The front of MaxHeap will contain the maximum element among the first half of the processed data when the array will be sorted.
The front of the MinHeap will contain the minimum element among the second half of the processed data when the array will be sorted.
Take out the top element of the MaxHeap if the total size of the current data stream so far is ODD.
Else take out the top two elements of the MaxHeap and MinHeap if the total size of the current data stream so far is even and take the average of them.
For the LeetCode problem, just return the Median as mentioned in steps 6 and 7.
And for the CodingNinja problem, push the median for each ith index in a vector and return them.
Time and Space Complexity:
Time Complexity: O(NlogN)
Space Complexity: O(N)
Code [C++]
class MedianFinder {
public:
priority_queue<int>first_half;
priority_queue<int, vector<int>, greater<int>>second_half;
MedianFinder() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
void addNum(int num) {
first_half.push(num);
int fqsize = first_half.size(), sqsize = second_half.size();
int total = fqsize + sqsize;
while((fqsize - sqsize) != ((total) & 1) && fqsize >= sqsize){
second_half.push(first_half.top()); first_half.pop();
fqsize = first_half.size(), sqsize = second_half.size();
}
if(fqsize && sqsize){
int ftop = first_half.top(), stop = second_half.top();
if(ftop > stop){
first_half.pop(), second_half.pop();
first_half.push(stop), second_half.push(ftop);
}
}
}
double findMedian() {
int fqsize = first_half.size(), sqsize = second_half.size();
if((fqsize + sqsize) & 1) return first_half.top() * 1.0;
else{
double sum = first_half.top() * 1.0 + second_half.top() * 1.0;
return sum / 2.0;
}
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/