346. Moving Average from Data Stream

This question asks how to efficiently calculate the average of the last size items. To do so, note that the window moving to the right requires popping the leftmost element and adding in a rightmost element. We can calculate the total sum in $O(1)$ by keeping the running sum and keep it $O(1)$ by making sure we can add and subtract to the total quickly — a deque allows you to pop from one end and add to one end quickly.

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.items = deque()
        self.total = 0
 
    def next(self, val: int) -> float:
        if len(self.items) == self.size:
            self.total -= self.items.popleft()
        self.items.append(val)
        self.total += val
        return self.total / len(self.items)