Efficient python solution using deque

  • 0

    I see another 4-line solution here but I don't think it is efficient. it has to do a sum (which is O(n)) each time calling next.
    instead, in my solution I keep a sum variable and every time I just need to do a O(1) update to it.

    class MovingAverage(object):

    def __init__(self, size):
        Initialize your data structure here.
        :type size: int
        self.maxsize = size
        self.sum = 0
        self.window = collections.deque()
    def next(self, val):
        :type val: int
        :rtype: float
        if len(self.window) < self.maxsize:
            self.sum += val
            self.sum += val - self.window.popleft()
        return self.sum/self.maxsize

    Your MovingAverage object will be instantiated and called as such:

    obj = MovingAverage(size)

    param_1 = obj.next(val)

  • 0

    Thank you for sharing the code.
    I was just wondering, when you return self.sum/self.maxsize, should it be self.sum/(len(self.window))?
    Also how do you deal with the float which the questions asked for instead of int?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.