Python solution with detailed explanation


  • 0
    G

    Solution

    Moving Average from Data Stream https://leetcode.com/problems/moving-average-from-data-stream/

    O(1) solution using deque

    • Use a deque to remove the oldest element.
    • Maintain the sum_so_far so that there is no need to recmopute it form scratch.
    from collections import deque
    class MovingAverage(object):
        def __init__(self, size):
            """
            Initialize your data structure here.
            :type size: int
            """
            self.q, self.size = deque(), size
            self.sum_so_far = 0
            return
            
        def next(self, val):
            """
            :type val: int
            :rtype: float
            """
            if len(self.q) == self.size:
                x = self.q.popleft()
                self.sum_so_far -= x
            self.q.append(val)
            self.sum_so_far += val
            return self.sum_so_far/float(len(self.q))
    

Log in to reply
 

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