
This video explains how to find median in a data stream.In this problem, given a stream of integers we are required to find median at any given point in a running integer also known as stream of integers.I have explained the problem with intuitive examples and i have also shown all the required intuition for solving the problem.I have first solved it using simple solution using sorting technique which is insertion sort.Later, I have shown the intuition for optimization and solved using 2 heaps. One maxheap containing left half values and the other as minheap containing the right half values of the ordered array.We can find median in constant time using the formula as I have shown for ODD and EVEN number of elements.
NOTES
CODE
class MedianFinder { public: priority_queue<int> maxheap; //1st half (left half) priority_queue<int,vector<int>,greater<int>> minheap; //2nd half (Right half) /** initialize your data structure here. */ MedianFinder() { } void addNum(int num) { int lsize = maxheap.size(); int rsize = minheap.size(); if(lsize==0) //num is the 1st element in stream maxheap.push(num); else if(lsize==rsize) //Push one element in maxheap for sure { if(num<minheap.top()) //num can be pushed to maxheap (1st half) to maintain order maxheap.push(num); else //Push root of minheap to maxheap (Push num to 2nd half) { int temp = minheap.top(); //Save root of minheap minheap.pop(); //Pop the root from minheap minheap.push(num); //Push num in minheap maxheap.push(temp); //Push the previous saved root of minheap in the maxheap } } else ///We assume that maxheap can be larger than minheap by a max of 1 element only { if(minheap.size()==0) { if(num>maxheap.top()) //Push num to 2nd half minheap.push(num); else //Push num to 1st half { int temp = maxheap.top(); maxheap.pop(); maxheap.push(num); minheap.push(temp); } } else if(num>=minheap.top()) //Push the element directly in minheap (2nd half) minheap.push(num); else //Push root of maxheap to minheap { if(num<maxheap.top()) //Push num to 1st half { int temp = maxheap.top(); //Save root of maxheap maxheap.pop(); //Pop root of maxheap maxheap.push(num); //Push num to maxheap minheap.push(temp); //Push previous saved root of maxheap to minheap } else //Push num to 2nd half minheap.push(num); } } } double findMedian() { int lsize = maxheap.size(); int rsize = minheap.size(); if(lsize > rsize) //Return top of maxheap for odd no of elements return double(maxheap.top()); else //Else return avg of top of maxheap and minheap return (double(maxheap.top())+double(minheap.top()))/2; } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
you are the best !💙
GREAT SOLUTION SIR !!.. just wanted to mention that condition in the line 41 is not required. I interpret it as this….since the max heap is already containing one element more than min heap so it is full. So if the new number is greater than top of max heap then it would surely go in the min heap only… and this condition has been given in the else part (line 52,53). we don’t need to check it with min heap’s top. Only case when an element can go into the max heap is when the new number is less than top of max heap, in which case we will do the transfer of maxheap().top in min heap and push the new number in max heap.