##### Short Problem Definition:

HackerLand National Bank has a simple policy for warning clients about possible fraudulent account activity. If the amount spent by a client on a particular day is *greater than or equal to* 2x the client’s median spending for a trailing number of days, they send the client a notification about potential fraud. The bank doesn’t send the client any notifications until they have at least that trailing number of prior days’ transaction data.

##### Link

Fraudulent Activity Notification

##### Complexity:

time complexity is O(N^2)

space complexity is O(N)

##### Execution:

I am not very happy with this solution, but it passes the tests, so I am posting it. This solution is running in O(N^2) due to the element removal from the running_median. del l[i] is O(N). O(NlogN) would be preferable.

The expenditures are actually not very large numbers [0..200], so there might be space for optimization there.

##### Solution:

```
from bisect import bisect_left, insort_left
def activityNotifications(expenditure, d):
warnings = 0
running_median = sorted(expenditure[:d])
for i,ele in enumerate(expenditure):
if i < d:
continue
if d % 2 == 1:
median = running_median[d//2]
else:
median = (running_median[d//2 - 1] + running_median[d//2])/float(2)
if ele >= median*2:
warnings += 1
# remove previous element
del running_median[bisect_left(running_median, expenditure[i-d])]
# add new element
insort_left(running_median, ele)
return warnings
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.