We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Fraudulent Activity Notifications
  5. Discussions

Fraudulent Activity Notifications

  • mss2518
     + 0 comments

    Similar to @coswaldors53 solution, the idea revolves around being limited to 200. If we maintain an array of the count of previous expenditures, to find the median we need to check at most 200 values for each expenditure, giving .

    We need to find the two indices where the median will lie - this will be , where we shift one to the right if is even. Then, we can sweep across the array to see when the number of values visited reaches this point. If we reach this point, then we know that we have found the index where the median lies.

    def activityNotifications(expenditure, d):
    hist = [0] * 200
    med_l = med_r = math.ceil(d / 2)
    if d % 2 == 0:
        med_r += 1
        
    for i in range(d):
        hist[expenditure[i]] += 1
    
    ans = 0  
    for i in range(d, len(expenditure)):
        events = 0
        curr_l = curr_r = -1
        for j in range(200):
            if curr_l == -1 and events + hist[j] >= med_l:
                curr_l = j
            if curr_r == -1 and events + hist[j] >= med_r:
                curr_r = j
            if curr_l != -1 and curr_r != -1:
                break
            events += hist[j]
 
        if expenditure[i] >= curr_l + curr_r:
            ans += 1
        hist[expenditure[i]] += 1
        hist[expenditure[i - d]] -= 1
        
    return ans