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.
time complexity is O(N^2)
space complexity is O(N)
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.
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.