Moving Average from Data Stream

QueueDesign

EasyLeetCode #346

15 min

Problem Statement

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 elements of the stream.

Example

Example 1:

Operation Sequence (size = 3):

next(1)returns: 1.000

next(10)returns: 5.500

next(3)returns: 4.667

next(5)returns: 6.000

Solution

A queue is a natural fit for this problem, as it allows us to easily maintain a sliding window of the most recent elements. We also keep a running sum to avoid recalculating the sum of the window every time.

Algorithm Steps

Initialize a queue and a variable for the running sum.
When a new value arrives, add it to the queue and the running sum.
If the queue size exceeds the window size, remove the oldest element from the queue and subtract it from the running sum.
The moving average is the running sum divided by the current number of elements in the queue.

Window (Queue)

State

Sum: 0

Average: 0.000

Start with an empty queue and sum = 0.

Moving Average from Data Stream Solution


from collections import deque

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

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