Solutions

1. Array or List

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = []

    def next(self, val: int) -> float:
        size, queue = self.size, self.queue
        queue.append(val)
        # calculate the sum of the moving window
        window_sum = sum(queue[-size:])

        return window_sum / min(len(queue), size)

Time & Space Complexity

Time complexity: $O(N \cdot M)$
Space complexity: $O(M)$

Where $N$ is the size of the moving window and $M$ is the number of calls made to next.

2. Double-ended Queue

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = deque()
        # number of elements seen so far
        self.window_sum = 0
        self.count = 0

    def next(self, val: int) -> float:
        self.count += 1
        # calculate the new sum by shifting the window
        self.queue.append(val)
        tail = self.queue.popleft() if self.count > self.size else 0

        self.window_sum = self.window_sum - tail + val

        return self.window_sum / min(self.size, self.count)

Time & Space Complexity

Time complexity: $O(M)$ $O (M)$
- Time complexity per next() call is $O(1)$ . Therefore, the total time complexity for $M$ calls is $O(M)$
Space complexity: $O(N)$

Where $N$ is the size of the moving window and $M$ is the number of calls made to next.

3. Circular Queue with Array

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.queue = [0] * self.size
        self.head = self.window_sum = 0

        # number of elements seen so far
        self.count = 0

    def next(self, val: int) -> float:
        self.count += 1

        # calculate the new sum by shifting the window
        tail = (self.head + 1) % self.size
        self.window_sum = self.window_sum - self.queue[tail] + val

        # move on to the next head
        self.head = (self.head + 1) % self.size
        self.queue[self.head] = val
        return self.window_sum / min(self.size, self.count)

Time & Space Complexity

Time complexity: $O(M)$ $O (M)$
- Time complexity per next() call is $O(1)$ . Therefore, the total time complexity for $M$ calls is $O(M)$
Space complexity: $O(N)$

Where $N$ is the size of the moving window and $M$ is the number of calls made to next.