Free Arrays lessonsArrays · Stage 8 · Sliding window · Step 2

Judge every window

Slide a fixed window and count the ones that pass a test. About 8 minutes.

Compare totals, not averages

A cricket selector wants every run of 3 matches where a batter averaged at least 40. Averages mean dividing, and dividing can mean fractions and rounding worries.

There's a neat way round it. An average of 3 scores is at least 40 exactly when their total is at least 3 × 40 = 120. So compare the window's total with the window size times the threshold, and everything stays in whole numbers.

Average at least t: means total at least size × t.

k = 3, threshold = 4, so a window needs sum ≥ 3 × 4 = 12

startend

sum: 6
need: 12
count: 0

First window: 2 + 2 + 2 = 6. Below 12, so it doesn't count.

Move 1 of 6

Test every window, including the first

Slide the window exactly as before. Test the first window before any sliding, then test again after every slide, counting the ones that pass.

A list of n numbers has n − k + 1 windows of size k. If your count ever comes out one short, it's almost always the first window that got skipped.

Don't skip the first window: test it before you slide.

In code

need = k * threshold
total = sum(nums[:k])
count = 1 if total >= need else 0
for right in range(k, len(nums)):
    total += nums[right] - nums[right - k]
    if total >= need:
        count += 1
return count

Quick check

Windows of 4 numbers, and the average must be at least 5. Which window totals pass?

ATotals of 20 or more
BTotals of 5 or more
COnly totals over 20

Show the answer

Totals of 20 or more. 4 × 5 = 20. A total of exactly 20 averages exactly 5, which counts.

Your problem

Count good windows

You get a list of numbers, a size k and a threshold. Count the runs of exactly k consecutive numbers whose average is at least the threshold.

Example

nums = [2, 2, 2, 2, 5, 5, 5, 8], k = 3, threshold = 4 → 3

1 ≤ k ≤ n ≤ 1,000,000 · 0 ≤ each value ≤ 10^6 · 0 ≤ threshold ≤ 10^6 · use longs

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.