Fraudulent Activity Notifications

• Time : O(nlogn)
• Space : O(d)

c++

int activityNotifications(vector<int> A, int d) {
    int res = 0, n = A.size();
    multiset<int> ms(begin(A), begin(A) + d);
    auto m = next(begin(ms), d / 2);

    for(int i = d; i < n; i++) {
        int median = *m + *prev(m, 1 - (d&1));
        if(A[i] >= median) res++;
        
        ms.insert(A[i]);
        if(A[i] < *m) m--;
        if(A[i-d] <= *m) m++;
        ms.erase(ms.find(A[i-d]));
    }
    return res;
}