We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Great Problem! Finally did it after some help from this discussion forum.
Important Points to be noted:
1) Use countsort
2) Avoid resorting again and again. Instead, just update the count by incrementing count of new element and decrementing count of old element. This count array will now store the counts of the last 'd' elements. Use this array to find the median of the last 'd' elements without using any O(d) loops which is actually O(n) and would result in timeout in many test cases. Only use loops which are constant in size i.e size of input range (201 in this case).
3) Since we need to compare the current element with 2*(median), avoid dividing the middle two elements in case when d is even and then multiply by 2. Instead just add them.
Here is my below solution in C++ which passes all test cases:
// Complete the activityNotifications function below.intgetTwiceMedian(vector<int>&A,vector<int>&count,intd){vector<int>countfreq(count);for(inti=1;i<countfreq.size();i++)// O(1);{countfreq[i]+=countfreq[i-1];}intmedian;inta=0;intb=0;//d is even -> median = a+bif(d%2==0){intfirst=d/2;intsecond=first+1;inti=0;for(;i<201;i++){if(first<=countfreq[i]){a=i;break;}}for(;i<201;i++){if(second<=countfreq[i]){b=i;break;}}}else//d is odd -> median = a + 0 = 2*(middle elem){intfirst=d/2+1;for(inti=0;i<201;i++){if(first<=countfreq[i]){a=2*i;break;}}}median=a+b;returnmedian;}intactivityNotifications(vector<int>A,intd){intalerts=0;vector<int>count(201,0);//stores count of last 'd' numbersintn=A.size();for(inti=0;i<d;i++){count[A[i]]++;}for(inti=d;i<n;i++){intmedian=getTwiceMedian(A,count,d);if(A[i]>=median)alerts++;//update count arraycount[A[i]]++;count[A[i-d]]--;}returnalerts;}
Fraudulent Activity Notifications
You are viewing a single comment's thread. Return to all comments →
Great Problem! Finally did it after some help from this discussion forum.
Important Points to be noted:
1) Use countsort
2) Avoid resorting again and again. Instead, just update the count by incrementing count of new element and decrementing count of old element. This count array will now store the counts of the last 'd' elements. Use this array to find the median of the last 'd' elements without using any O(d) loops which is actually O(n) and would result in timeout in many test cases. Only use loops which are constant in size i.e size of input range (201 in this case).
3) Since we need to compare the current element with 2*(median), avoid dividing the middle two elements in case when d is even and then multiply by 2. Instead just add them.
Here is my below solution in C++ which passes all test cases: