Leetcode 3466: Moving Average from Data Stream

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Code

class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.size = size
        self.vals = [0]* size
        self.cnt = 0
        self.sum = 0

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.cnt += 1
        idx = (self.cnt - 1) % self.size 

        # replace old value
        self.sum -= self.vals[idx]
        self.sum += val
        self.vals[idx] = val

        return float(self.sum) / self.cnt if self.cnt < self.size \
            else float(self.sum) / self.size

# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

Idea

A cyclic list

You can also use deque however when you calculate average it takes O(K) time where K is the window size.: https://discuss.leetcode.com/topic/44116/4-line-python-solution-using-deque