Sliding Window Average

Reuse the previous window sum instead of recomputing all n elements.

1. Slide the window

2. Current window

Sum

Average

3. Sliding-window update

Output array B

There are m − n + 1 valid windows.

Key idea

First window:

windowSum = A[0] + A[1] + ... + A[n-1]

Then slide one position:

newSum = oldSum − A[left] + A[right]

B[i] = windowSum / n

Complexity

Naive approach

Recalculate all n elements for every window.

O(mn)
Sliding window

Remove one value and add one value for each move.

O(m)