043. Moving Average Stream

Why this mechanism works

A stream cannot subtract the departing value unless it remembers it. A FIFO deque stores the recent values and a running sum avoids repeated summation. Remove the oldest value only when the new insertion exceeds the capacity.

State and boundaries

window contains the latest at-most-k values in arrival order. total is their sum.

Protocol

1. Append the incoming value and add it to total.
2. If size exceeds k, pop the oldest and subtract it.
3. Divide by the repaired window size.
4. Append the average.

Visualization

k=3, incoming 1,10,3,5
windows: [1], [1,10], [1,10,3], [10,3,5]
divisors: 1,2,3,3

Python implementation

from collections import deque

def moving_averages(values, k):
    if k < 1:
        raise ValueError('k must be positive')
    window = deque()
    total = 0
    output = []
    for value in values:
        window.append(value)
        total += value
        if len(window) > k:
            total -= window.popleft()
        output.append(total / len(window))
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 moving_averages: if k < 1:
values=[1, 10, 3, 5]; k=3

L6 moving_averages: window = deque()
values=[1, 10, 3, 5]; k=3; window=deque([])

L7 moving_averages: total = 0
values=[1, 10, 3, 5]; k=3; window=deque([]); total=0

L8 moving_averages: output = []
values=[1, 10, 3, 5]; k=3; window=deque([]); total=0; output=[]

L9 moving_averages: for value in values:
values=[1, 10, 3, 5]; k=3; window=deque([]); total=0; output=[]; value=1

L10 moving_averages: window.append(value)
values=[1, 10, 3, 5]; k=3; window=deque([1]); total=0; output=[]; value=1

L11 moving_averages: total += value
values=[1, 10, 3, 5]; k=3; window=deque([1]); total=1; output=[]; value=1

L14 moving_averages: output.append(total / len(window))
values=[1, 10, 3, 5]; k=3; window=deque([1]); total=1; output=[1.0]; value=1

... 9 intermediate state changes omitted ...

L10 moving_averages: window.append(value)
values=[1, 10, 3, 5]; k=3; window=deque([1, 10, 3, 5]); total=14; output=[1.0, 5.5, 4.666666666666667]; value=5

L11 moving_averages: total += value
values=[1, 10, 3, 5]; k=3; window=deque([1, 10, 3, 5]); total=19; output=[1.0, 5.5, 4.666666666666667]; value=5

L13 moving_averages: total -= window.popleft()
values=[1, 10, 3, 5]; k=3; window=deque([10, 3, 5]); total=18; output=[1.0, 5.5, 4.666666666666667]; value=5

L14 moving_averages: output.append(total / len(window))
values=[1, 10, 3, 5]; k=3; window=deque([10, 3, 5]); total=18; output=[1.0, 5.5, 4.666666666666667, 6.0]; value=5

L4 moving_averages: if k < 1:
values=[]; k=2

L6 moving_averages: window = deque()
values=[]; k=2; window=deque([])

L7 moving_averages: total = 0
values=[]; k=2; window=deque([]); total=0

L8 moving_averages: output = []
values=[]; k=2; window=deque([]); total=0; output=[]

Why the solution is correct

After insertion there can be only one excess value. Removing the oldest restores exactly the most recent k values, or keeps the entire shorter prefix during warm-up. The sum tracks those same values, making the quotient correct.

Time and space

O(n) time; O(k) queue space plus O(n) output. Floating-point averages have ordinary numeric rounding limits.

Common mistakes

Dividing by k during warm-up biases early averages. A list pop(0) introduces linear shifts per removal.

Reasoning card

Transfer exercise

Turn the function into a class with a next(value) method, preserving the exact same window invariant.