346. Moving Average from Data Stream

Problem¶

Maintain a stream of integers. After each insertion, return the average of the last size values, or all values so far if fewer have arrived.

size = 3
next(val)    window        result
next(1)     [1]           1.0
next(10)    [1, 10]       5.5
next(3)     [1, 10, 3]    4.66667
next(5)     [10, 3, 5]    6.0

class MovingAverage:
    def __init__(self, size: int):
        pass

    def next(self, val: int) -> float:
        pass

Key trick¶

Keep a FIFO queue and a running sum; subtract the oldest value when the window exceeds its capacity.

Trap¶

• Divide by the current window length, not always by size.
• Avoid recomputing the sum or using list.pop(0): both take \(O(\text{size})\) per call.
• A bounded deque silently discards values, so capture the outgoing value before updating the sum.

Why is it interesting?¶

It turns repeated aggregation into constant-time updates by retaining only the state needed for the next answer.

Python solution¶

from collections import deque


class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.q = deque()
        self.total = 0

    def next(self, val: int) -> float:
        self.q.append(val)
        self.total += val

        if len(self.q) > self.size:
            self.total -= self.q.popleft()

        return self.total / len(self.q)

Time: \(O(1)\) per next call. Space: \(O(\text{size})\).

Comment on my solution¶

Your solution is correct and interview-ready: it uses a running sum, evicts the oldest value, and handles partially filled windows correctly. It already achieves \(O(1)\) time per call and \(O(\text{size})\) space; the only useful polish is adding the -> float return annotation.

from collections import deque


class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.window_sum = 0
        self.q = deque()

    def next(self, val: int):
        self.q.append(val)
        self.window_sum += val
        if len(self.q) > self.size:
            self.window_sum -= self.q.popleft()
        return self.window_sum / len(self.q)

Extra¶

Problem description¶

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window size.
• double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

Constraints:

• 1 <= size <= 1000
• -10^5 <= val <= 10^5
• At most 10^4 calls will be made to next.