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();
 */