median in a running stream help

general
, ,
1

I am trying to do this question on leetcode. When I am using multiset for the problem I am getting TLE on last test case. However on using two heaps I am getting AC. Can someone please tell me why using multiset is giving TLE. Here is my code.

class MedianFinder 
{

public:

    multiset <int> s;
    MedianFinder() 
    {
        
    }
    
    void addNum(int num) 
    {
        s.insert(num);
    }
    
    double findMedian() 
    {
        int n=s.size();
        auto it=next(s.begin(),(n+1)/2-1);
        if(n%2!=0)
            return *it;
        else
        {
            double ans;
            ans=( *it + *next(it,1))/2.0;
            return ans;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
2

“auto it=next(s.begin(),(n+1)/2-1);” it is linear. That’s why you are getting TLE.

Instead you can use binary search to get a better time complexity. Binary search for the answer and the query you need to answer at each step (how many elements is less than the current one) you can do that with the help of PBDS of c++ (or can make your own AVL or RED-Black tree).

1 Like
3

Thanks for the intel sire:)