How many k-minute windows beat the target average?

Question

Given a series of readings arr, a window length k, and a threshold, count how many windows of exactly k consecutive readings have an average of at least threshold. Return the count of qualifying windows. Aim for O(n).

Accepted Answer

"Average at least threshold" is the same as "sum at least k threshold," so precompute the target sum once and never divide (this also sidesteps floating-point rounding). Then slide the window, updating the running sum by the element that enters minus the element that leaves. Trace with target = 12. Window sums run 6, 6, 9, 12, 15, 18. The last three (12, 15, 18) clear 12, so the answer is 3. Time O(n), space O(1). Takeaway. Turn a per-window average test into a fixed sum comparison up front, then let the sliding sum do the work. Comparing scaled integers instead of dividing every window is bo…

How many k-minute windows beat the target average?

Your answer

More Coding questions