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

2 comment on “Median from data stream”

  • Tech Dose August 8, 2021

    you are the best !💙

  • Tech Dose October 14, 2022

    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.

Write a comment