import java.io.; import java.util.; import java.util.stream.*;

class Result {

public static int activityNotifications(List<Integer> expenditure, int d) {
    int notifications = 0;
    int[] count = new int[201]; // expenditure[i] <= 200

    for (int i = 0; i < d; i++) {
        count[expenditure.get(i)]++;
    }

    for (int i = d; i < expenditure.size(); i++) {
        double median = getMedian(count, d);
        if (expenditure.get(i) >= 2 * median) {
            notifications++;
        }

        // Slide the window
        count[expenditure.get(i - d)]--;
        count[expenditure.get(i)]++;
    }

    return notifications;
}

private static double getMedian(int[] count, int d) {
    int sum = 0;
    if (d % 2 == 1) {
        int mid = d / 2 + 1;
        for (int i = 0; i < count.length; i++) {
            sum += count[i];
            if (sum >= mid) return i;
        }
    } else {
        int mid1 = d / 2;
        int mid2 = mid1 + 1;
        int m1 = -1, m2 = -1;
        for (int i = 0; i < count.length; i++) {
            sum += count[i];
            if (sum >= mid1 && m1 == -1) m1 = i;
            if (sum >= mid2) {
                m2 = i;
                break;
            }
        }
        return (m1 + m2) / 2.0;
    }
    return 0;
}

}

public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    String[] firstMultipleInput = bufferedReader.readLine().trim().split(" ");
    int n = Integer.parseInt(firstMultipleInput[0]);
    int d = Integer.parseInt(firstMultipleInput[1]);

    List<Integer> expenditure = Arrays.stream(bufferedReader.readLine().trim().split(" "))
        .map(Integer::parseInt)
        .collect(Collectors.toList());

    int result = Result.activityNotifications(expenditure, d);

    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

    bufferedReader.close();
    bufferedWriter.close();
}

}

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
            
        

My Kotlin version, which sorts the first d elements once, and then adopts binary search to remove/insert old/new elements as the window slides;

fun insertInSortedList(items: MutableList<Int>, newElement: Int) {
    val index = items.binarySearch(newElement).let { if (it < 0) -it - 1 else it }
    items.add(index, newElement)
}

fun removeItemFromSortedList(sortedList: MutableList<Int>, item: Int) {
    val index = sortedList.binarySearch(item)
    if (index >= 0) {
        sortedList.removeAt(index)
    }
}

fun median(values: List<Int>): Double {
    if (values.isEmpty()){
        return 0.0
    }
    return if (values.size % 2 == 0) {
        (values[values.size / 2-1] + values[values.size/2])/2.0

    } else {
        values[values.size/2].toDouble()
    }
}

fun activityNotifications(expenditure: Array<Int>, d: Int): Int {
    var numberOfNotifications = 0
    var startIndex = 0
    var valueToCheckIndex = d
    var sublist = expenditure.slice(startIndex..valueToCheckIndex-1).sorted().toMutableList()
    while (valueToCheckIndex < expenditure.size) {
        val m = median(sublist)
        val valueToCheck = expenditure[valueToCheckIndex]
        if (valueToCheck >= 2*m) {
            ++numberOfNotifications
        }
        removeItemFromSortedList(sublist, expenditure[startIndex])
        insertInSortedList(sublist, expenditure[valueToCheckIndex])
        ++startIndex
        ++valueToCheckIndex
    }
    return numberOfNotifications
}

public static int activityNotifications(List expenditure, int d) { int notifications = 0; int[] count = new int[expenditure.stream().max(Integer::compareTo).get() + 1];

    for (int i = 0; i < d; i++) {
        count[expenditure.get(i)]++;
    }

    for (int i = d; i < expenditure.size(); i++) {
        double median = getMedian(count, d);

        if (expenditure.get(i) >= 2 * median) {
            notifications++;
        }

        count[expenditure.get(i - d)]--;
        count[expenditure.get(i)]++;
    }

    return notifications;
}

private static double getMedian(int[] count, int d) {
    int sum = 0;
    int mid1 = -1, mid2 = -1;
    boolean even = d % 2 == 0;
    int mid = d / 2;

    for (int i = 0; i < count.length; i++) {
        sum += count[i];

        if (even) {
            if (mid1 == -1 && sum >= mid)
                mid1 = i;
            if (mid2 == -1 && sum >= mid + 1) {
                mid2 = i;
                return (mid1 + mid2) / 2.0;
            }
        } else {
            if (sum > mid)
                return i;
        }
    }
    return 0;
}

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