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