Moving Average Filter

easyFREESliding WindowSliding Window, Signal ProcessingCV - DSA

Problem Statement

A Moving Average Filter (also called a box filter) is one of the simplest smoothing techniques in image and signal processing. It replaces each pixel with the average of its neighboring pixels within a window.

Given a 1D signal (list of integers) and a window size k, compute the moving average for each valid position. Return the result as a list of floats rounded to 2 decimal places.

Application in CV

Noise reduction in images (applied row-wise or column-wise)
Temporal smoothing in video frames
Pre-processing before edge detection

Constraints

$1 \leq len(signal) \leq 10000$
$1 \leq k \leq len(signal)$
$-10000 \leq signal[i] \leq 10000$

Example

Input

signal = [1, 2, 3, 4, 5], k = 3

Output

[2.0, 3.0, 4.0]

Reasoning

Input: signal is a sequence of $n = 5$ samples, $x_1, \dots, x_5 = 1, 2, 3, 4, 5$ , and k $= 3$ is the window width: how many consecutive samples are averaged together.
Valid positions: a window only counts if all $k$ of its samples lie inside the signal, so it can start at sample 1, 2 or 3. That gives $n - k + 1 = 5 - 3 + 1 = 3$ outputs.
Math: the output at window $j$ is $y_j = \frac{1}{k}\sum_{i=j}^{j+k-1} x_i$ . Here $y_1 = \frac{1+2+3}{3} = 2$ , $y_2 = \frac{2+3+4}{3} = 3$ , $y_3 = \frac{3+4+5}{3} = 4$ .
Output: each average is a float rounded to 2 decimal places, giving [2.0, 3.0, 4.0].
Notice: the output is $k - 1 = 2$ samples shorter than the input, because the edges are never padded. On a straight line like this one, each smoothed value equals the window's centre sample ( $2, 3, 4$ ), so averaging leaves a linear trend unchanged.

Learn this in

Two Pointers & Sliding WindowDSA Study Plan CNNs & Sequence ModelsML Study Plan

More from CV - DSA

Concept primer

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:

y_i = \frac{1}{k} \sum_{j=i}^{i+k-1} x_j, \quad i = 0, 1, \dots, n-k

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

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

Method	Pros	Cons	When to use
Naive sum	Simple, no edge cases	O(nk) slow for k ≈ n	k small (< 100)
Prefix sum	O(n), clean code	Extra O(n) space	General case
Recursive	O(n), O(1) space	Init overhead	Memory-tight

Compute averages: Generate list of length $n-k+1$ .
Format output: Convert to float, round to 2 decimals.
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

Approach	Time	Space	Notes
Naive	O(nk)	O(n) output	10^4 × 10^4 = 10^8 → borderline
Prefix/Recursive	O(n)	O(n) / O(1) extra	Optimal, scales perfectly
Output	-	O(n-k+1) = O(n)	Always required

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

solution.py

Python 3.13

Test results