< Back





346. Moving Average from Data Stream

An interesting problem because we're maintaining the average of a sliding window from a data stream,
we're not given the values wholesale in one input. We're given the size of the sliding window to
maintain the moving average within. When the class's .next method is called, we're provided with an
integer to update the sliding window. This will cause the moving average to update as well, however,
we need to maintain the size of the sliding window.

We solve this by maintaining the sliding window in a queue. If the queue reaches capacity, we pop off
in FIFO order the oldest value of the sliding window. We subtract the popped value from the running
sum while also adding the new value, updating the running sum.

Finally, we return the running sum divided by the length of the queue to get the moving average.

The solution is as follows:


  from collections import deque
  class MovingAverage:
      def __init__(self, size: int):
          self.size = size
          self.queue = deque()
          self.window_sum = self.count = 0

      def next(self, val: int) -> float:
          self.count += 1
          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 Complexity:

  O(1) - Popping from the queue and calculating the moving average happens in constant time.

_ Space Complexity:

  O(n) - The sliding window is size n.