Moving Average Filter

1. Background Knowledge

The moving average filter (MAF) is a fundamental low-pass filter in signal processing that smooths data by replacing each value with the average of neighboring values in a fixed-size window of length $k$. For a 1D signal $x = [x_0, x_1, \dots, x_{n-1}]$, the output $y_i$ at position $i$ is:

This produces $n - k + 1$ values, reducing high-frequency noise while preserving low-frequency trends. In computer vision (CV), it's applied row/column-wise for image denoising before tasks like edge detection (e.g., Canny). Prerequisites: basic array indexing, summation, floating-point division, and rounding to 2 decimals (round(value, 2) in Python).

2. Algorithm Approach

Naive approach: For each $i$, sum $k$ elements directly → $O(nk)$ time, acceptable for $n \leq 10^4$, $k \leq n$.

Optimized sliding window: Use a prefix sum array $s = 0$, $s[i+1] = s[i] + x_i$. Then $y_i = \frac{s[i+k] - s[i]}{k}$:

• Build prefix: $O(n)$
• Query each window: $O(1)$
• Total: $O(n)$

Recursive (cumulative average): Maintain running sum $sum$, update $sum = sum - x[i-1] + x[i+k-1]$ → $O(n)$ after $O(k)$ init. Both optimizations beat naive for large $k$.

3. Step-by-Step Strategy

1. Validate inputs: Ensure $1 \leq k \leq n$, $n = \text{len}(signal)$.
2. Choose method:

3. Compute averages: Generate list of length $n-k+1$.
4. Format output: Convert to float, round to 2 decimals.
5. Test edge cases: $k=1$ (identity), $k=n$ (single avg).

Python prefix sum example:

def moving_average(signal, k):
 n = len(signal)
 if k > n or k < 1: raise ValueError("Invalid k")
 prefix = * (n + 1)
 for i in range(n):
 prefix[i+1] = prefix[i] + signal[i]
 return [round((prefix[i+k] - prefix[i]) / k, 2) for i in range(n - k + 1)]

4. Common Pitfalls

• Off-by-one indexing: Window ends at $i+k-1$, output length $n-k+1$ (not $n$).
• Integer division: Use float division (/k not //k); signal ints → avg float.
• Rounding: Apply round(avg, 2) after averaging, not per element.
• Edge handling: No padding specified → valid positions only (drop first/last incomplete windows).
• Empty/zero cases: $n=1, k=1$ → [signal]; negative values OK per constraints.
• Performance: Naive fails $T.C.$ for $n=10^4, k=10^4$ ($10^8$ ops → timeout).

5. Time & Space Complexity

Best: Prefix sum for clarity, recursive for space. Both handle constraints efficiently.