Fraudulent Activity Notifications

  • + 0 comments

    O(n*d) solution with Python bisect. Clean, readable code.

    import bisect
    
    def activityNotifications(expenditure, d):
        warns = 0
        # Initialize sorted trailing window
        trailing = sorted(expenditure[:d])
    
        for today in range(d, len(expenditure)):
            # Get median from sorted trailing list
            if d % 2 == 1:
                median = trailing[d // 2]
            else:
                median = (trailing[d // 2] + trailing[d // 2 - 1]) / 2
    
            if expenditure[today] >= 2 * median:
                warns += 1
    
            # Slide the window
            # Remove the element going out of the window
            old_value = expenditure[today - d]
            del trailing[bisect.bisect_left(trailing, old_value)]
    
            # Insert the new value to maintain sorted order
            bisect.insort(trailing, expenditure[today])
    
        return warns