Fraudulent Activity Notifications

  • + 0 comments

    Calculate median on the fly utilizing the fact that all expenditures are below 200 (reducing the problem to find median in Counter of integers)

    def activityNotifications(expenditure, d):
        counts = [0] * 200
        exp = expenditure
    
        for x in exp[:d]:
            counts[x] += 1
    
        def M():
            total_left = 0
            for l in range(200):
                total_left += counts[l]
                if total_left > d - total_left:
                    return l
                elif total_left == d - total_left:
                    r = l + 1
                    while not counts[r]: 
                        r += 1
                    return (l + r) / 2.
    
        res = 0
        for i in range(d, len(exp)):
            res += (exp[i] >= M() * 2)
            counts[exp[i-d]] -= 1
            counts[exp[i]] += 1
            
        return res