# Fraudulent Activity Notifications

# Fraudulent Activity Notifications

+ 49 comments 4 thoughts that may help:

1.) Counting sort

2.) A Queue

3.) Pay attention to the even case.

4.) Integer division is a blessing and a curse, be careful.

I really enjoyed this problem :) It's an extremely practical use of the material, a little tricky, but very doable with some good thought and planning. I wish more problems were this well conceived!

+ 24 comments Didn't see any JavaScript solutions, so here comes mine:

function activityNotifications (expenditure, d) { // Number of notifications let n = 0 // Set midpoints for median calculation let [ i1, i2 ] = [ Math.floor((d-1)/2), Math.ceil((d-1)/2) ] let m1, m2, m // Initialize count sorted subarray let cs = new Array(201).fill(0) for (let i = d-1; i >= 0; i--) cs[expenditure[i]]++ // Iterate through expenditures for (let i = d, l = expenditure.length; i < l; i++) { // Find median for (let j = 0, k = 0; k <= i1; k += cs[j], j++) m1 = j for (let j = 0, k = 0; k <= i2; k += cs[j], j++) m2 = j let m = (m1 + m2) / 2 // Check if notification is given if (expenditure[i] >= m * 2) n++ // Replace subarray elements cs[expenditure[i-d]]-- cs[expenditure[i]]++ } return n }

It can be optimized by simplifying some redundant calculations, but I wrote it this way to make the code easier to follow and understand ;)

+ 20 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:

// Complete the activityNotifications function below. int getTwiceMedian( vector<int> &A, vector<int> &count,int d) { vector<int> countfreq(count); for(int i=1; i< countfreq.size(); i++)// O(1); { countfreq[i] += countfreq[i-1]; } int median; int a = 0; int b = 0; //d is even -> median = a+b if(d%2==0){ int first = d/2; int second = first+1; int i = 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) { int first = d/2 + 1; for(int i=0;i<201;i++){ if(first<=countfreq[i]){ a = 2*i; break; } } } median = a + b; return median; } int activityNotifications(vector<int> A, int d) { int alerts = 0; vector<int> count(201, 0); //stores count of last 'd' numbers int n = A.size(); for(int i =0; i<d; i++) { count[A[i]]++; } for(int i=d; i< n; i++) { int median = getTwiceMedian(A, count, d); if(A[i]>= median) alerts++; //update count array count[A[i]]++; count[A[i-d]]--; } return alerts; }

+ 15 comments For python users, I achieved an astonishing speed improvemets by using the bisect module, and keeping a tab of the numbers to insert and delete from the fixed length sliding window:

The element to remove is always present in the window, so the bisect module can help to find its postion in sorted array (the elements of the window is needed to be sorted to find median).

The bisect can then be used to insert the inserting number into the sorted window, keeping it sorted on insert.

Achieved O(n) solution time, mainly due ot moving the list elemets at insert and remove; additional O(log n) due to bisect is minimal and can be ignored.

+ 17 comments Java 7 solution. Applied the idea of Counting sort

// Complete the activityNotifications function below. static int activityNotifications(int[] expenditure, int d) {; int notificationCount = 0; int[] data = new int[201]; for (int i = 0; i < d; i++) { data[expenditure[i]]++; } for (int i = d; i < expenditure.length; i++) { double median = getMedian(d, data); if (expenditure[i] >= 2 * median) { notificationCount++; } data[expenditure[i]]++; data[expenditure[i - d]]--; } return notificationCount; } private static double getMedian(int d, int[] data) { double median = 0; if (d % 2 == 0) { Integer m1 = null; Integer m2 = null; int count = 0; for (int j = 0; j < data.length; j++) { count += data[j]; if (m1 == null && count >= d/2) { m1 = j; } if (m2 == null && count >= d/2 + 1) { m2 = j; break; } } median = (m1 + m2) / 2.0; } else { int count = 0; for (int j = 0; j < data.length; j++) { count += data[j]; if (count > d/2) { median = j; break; } } } return median; }

Sort 967 Discussions, By:

Please Login in order to post a comment