Count windows whose average beats a threshold

Question

Given a series of values and a window length k, count how many windows of k consecutive values have a mean strictly greater than a threshold T. Return the number of qualifying windows. Aim for O(n).

Accepted Answer

A window's mean exceeds T exactly when its sum exceeds k T, so you can compare sums and avoid dividing each time. Compute the first window's sum, then slide: each step adds the entering value and subtracts the leaving one, an O(1) update. Count each window whose sum clears k T. Tracing [1, 2, 3, 4] with k = 2, T = 2.5: window sums are 3, 5, 7, and k T = 5. Only the last (7) is strictly greater, so the count is 1. Time O(n), space O(1). Comparing against k T instead of dividing keeps the arithmetic exact for integers and dodges floating-point wobble. Assumes k <= len(values); guard if empty wi…

Count windows whose average beats a threshold

Your answer

More Coding questions