My thoughts i maintained two heaps O(Nlog d) Solution

//////////Vinayak Sangar /////////////

If d is ODD

First is a max heap of size (d/2)+1 to keep record of the first (d/2)+1 minimum elements of the array of size d Alongside i kept a second min heap of size (d/2) to keep record of last d/2 maximum elemnts of the array of size d

If d is EVEN

First is a max heap of size (d/2)+1 to keep record of the first (d/2)+1 minimum elements of the array of size d Alongside i kept a second min heap of size (d/2)-1 to keep record of last d/2 maximum elemnts of the array of size

THEN every time the top element of max heap will be the median in case of odd and in even the first two elements of the max heap will be the median in case of even

THEN WHY WE NEED TWO HEAPS ??????????

HOW TO MANAGE HEAPS

Suppose as in the input example 1 and i am maintaining heaps using multiset .

*Side Notes on Multiset * (Max heap implemented by removing elements from last of the multiset and min heap by removing from beginning and multiset to allow for multiple keys Warning: removing elements from multiset by element value removes all occurences so remove by iterator)

Input

9 5

2 3 4 2 3 6 8 4 5

Last d days include 2 3 4 2 3

My max heap will look like 2 2 3

and min heap will look like 3 4

Median will be 3 and current transaction 6

*Now * we need to remove 2(arr[j]) from the record and add 6(arr[i]) and consider another d days . Here we need another heap .Let if removed element be arr[j] and its present in first heap and new element can be added to any of the two heaps

Keep in mind two things

1)we have to manage two heaps or multisets if you can say in such a way as the size of first remains constant of (d/2 + 1) and seconds size also remains constant ie d/2

2) we have to maintain the order of the elements like we are maintaining a zig zag sorted array i mean half sorted first in first multiset rest half in second multiset

ex for input array d 2 3 4 2 3

2 2 3

3 4

Here st1 is max heap 2 2 3 Here st2 is my min heap 3 4 arr[i] is new element to be added ie 6 arr[j] is element to be removed ie 2

if(st1.find(arr[j]) != st1.end())
            {
                st1.erase(st1.find(arr[j]));
                it = st2.begin();
                if(arr[i] >= (*it))
                {st1.insert((*it));st2.erase(it);st2.insert(arr[i]);}
                else
                    st1.insert(arr[i]);
            }
            else 
            {
                st2.erase(st2.find(arr[j]));
                it = --st1.end();
                if(arr[i] <= (*it))
                {st2.insert(*it);st1.erase(it);st1.insert(arr[i]);}
                else st2.insert(arr[i]);
            }

This way using two heaps we can solve this problem in O(Nlogd)

My submission

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/submissions/code/36535760

Thanks