EasyDesignQueueArrayData Stream

Moving Average from Data Stream

1 approach, code in every language

You receive a stream of integers one value at a time and must report the average of a sliding window of the most recent values.

Implement the MovingAverage class. The constructor MovingAverage(size) fixes the window width. The method next(val) appends val to the stream and returns the average of the last size values seen so far.

Before the stream has produced size values, the average is taken over however many values have arrived.

Example 1

Input: ["MovingAverage","next","next","next","next"] [[3],[1],[10],[3],[5]]

Output: [null,1.0,5.5,4.66667,6.0]

Window size 3. next(1) averages [1] = 1.0; next(10) averages [1,10] = 5.5; next(3) averages [1,10,3] = 4.66667; next(5) drops 1 and averages [10,3,5] = 6.0.

Example 2

Input: ["MovingAverage","next","next"] [[1],[4],[8]]

Output: [null,4.0,8.0]

With window size 1 each call reports only the latest value, so next(4) = 4.0 and next(8) = 8.0.

Constraints

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

Queue With Running Sum

Track the window in a FIFO queue and keep a running total so each average is a single division.

Loading animation…

Intuition

Recomputing the sum of the window from scratch on every call would waste work when only one value enters and one leaves. Instead we maintain a running sum and a queue holding exactly the values currently inside the window. On each call we enqueue the new value and add it to the sum. If the queue now exceeds the target width, we dequeue the oldest value and subtract it from the sum. Dividing the running sum by the current queue length gives the moving average in constant time.

Algorithm walkthrough

1Store the window size, an empty queue, and a running sum of 0 in the constructor.
2On next(val), push val onto the back of the queue and add it to the running sum.
3If the queue length now exceeds size, pop the front value and subtract it from the running sum.
4Compute the average as the running sum divided by the current queue length.
5Return that average, using floating-point division so partial windows report correctly.

Implementation

from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        self.running_sum = 0

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

Time

O(1) per call to next

Space

O(size)

The queue never holds more than size elements, and the running sum turns each average into one subtraction and one division.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free