Hey, I find your comment to be very usefull, but there's 1 thing I didn't got, why saving bigger elements in minHeap and smaller elements in maxHeap. Thanks in advance!!

Thanks for the help, was timed-out before using your little trick :-p

Agreed, the solution was (somewhat) obvious...my dumbass kept getting errors due to the fact that Java does not automatically convert int's to doubles/float in printf...

"for inserting first two elements, insert bigger element in minHeap and smaller in maxHeap". No need to insert the first 2 elements in this way, just set the median to zero in the beginning and do everything as mentioned inside the loop.

Here is the implementation in c++

vector<double> runningMedian(vector<int> a) {
        vector<double> res;
        priority_queue<int, vector<int>, greater<int>> minheap;
        priority_queue<int> maxheap;

        double median = 0;

        for (int i=0; i<a.size(); i++) {
                if (a[i] <= median) {
                        maxheap.push(a[i]);
                } else {
                        minheap.push(a[i]);
                }

                if (minheap.size() > maxheap.size()+1) {
                        maxheap.push(minheap.top());
                        minheap.pop();
                }
                if (maxheap.size() > minheap.size()+1) {
                        minheap.push(maxheap.top());
                        maxheap.pop();
                }

                if (minheap.size() == maxheap.size()) {
                        median = (maxheap.top() + minheap.top())/2.0;
                } else if(minheap.size() > maxheap.size()) {
                        median = (double)minheap.top();
                } else if (minheap.size() < maxheap.size()) {
                        median = (double)maxheap.top();
                }
                res.push_back(median);
        }
        return res;
}

I am coding in cpp, my answer is correct but there is some problem in type casting an int to double, can anyone help me with this?

https://hastebin.com/ujaridapum.cpp

WOW

Woah, buddy! I did the same thing and timed out in most of the test cases.

I did the same thing, and got similar result. The comparison of maximum running time between sorted array + binary search vs double heaps is like 0.42s vs 0.05s. Implemented in C++.

How did you measure the running time?

Here is my code, and all the test cases have failed except the first one.

    int n = a.length;

    double[] db = new double[n];
    PriorityQueue<Integer> minh = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxh = new PriorityQueue<Integer>(Collections.reverseOrder());
    for(int i=0; i<n; i++){
        if(maxh.isEmpty()){
            maxh.add(a[i]);
        }
        else if(maxh.size() == minh.size()){
            if(n<minh.peek())
                maxh.add(a[i]);
            else{
                minh.add(a[i]);
                maxh.add(minh.poll());
            }
        }
        else if(maxh.size() > minh.size()){
            if(n > maxh.peek()){
                minh.add(a[i]);
            }
            else{
                maxh.add(a[i]);
                minh.add(maxh.poll());

            }

        }
        if(maxh.size() == minh.size())
            db[i] = (maxh.peek() + minh.peek())/2.0;
        else
            db[i] = (maxh.peek());


    }
        return db;

I made some heavy revisions to this challenge today. Hopefully it's clearer now!

you cant solve the problem using Insertion sort in the given time constraints .

Heap didnt striked me at first , i actually used binary search for insertion rather than insertion sort. Got TLE in only 4 test cases .

But still the problem is designed to use Heap . so "if I want to use insertion sort method only, no heaps." this is not a healthy attitude .

If you aren't into heaps like above comments suggest. Try thinking about how you are inserting into the list. Would it be quicker to smartly insert instead of sorting after every insert.

are you using Insertion sort or somrthing like that

You are on a heap challenge! =P

Try to determine how you can use heaps to solve the problem. Keeping all elements in a min heap would allow you to keep track of the smallest integer, whereas a max heap would let you keep track of the largest. How can you combine these ideas so you have easy access to the median element(s)?

so, what is your time complexity of your method? consider the worst case, you have to compare each former number, so O(n) for each input. when n is big, your algorithm will become more and more slower in linear. In fact, you do not need the binary search tree and you do not have to compare each pair of numbers even in the worst case. in fact, you only care about the numbers in the middle of the input array, using 2 heaps, the time complexity is O(logn) for each input. the hardest point may be which heap should be inserted in and what adpation should be made when the new input comes.