HackerRank 'Fraudulent Activity Notifications' Solution

Martin Kysel · August 28, 2020

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.

Fraudulent Activity Notification


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:
        if d % 2 == 1:
            median = running_median[d//2]
            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

Twitter, Facebook