Moving Average From Data Stream - Leetcode Solution

Problem statement:

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1 // return 1.00000
m.next(10) = (1 + 10) / 2 // return 5.50000
m.next(3) = (1 + 10 + 3) / 3 // return 4.66667
m.next(5) = (10 + 3 + 5) / 3 // return 6.00000

Solution:

The problem requires us to keep track of a moving average of a stream of integers. We need to be able to add the incoming integers one by one, and calculate the average for each window.

We can solve the problem by using a queue to keep track of the window of integers. Whenever we add a new integer, we remove the oldest integer from the queue if the queue size exceeds the window size, and calculate the average of all integers in the queue.

To calculate the average, we need to keep track of the sum of all integers in the queue. Whenever we add or remove an integer, we update the sum and calculate the average.

We can implement the solution using a class MovingAverage that has two instance variables - a queue to keep track of the window of integers, and a sum to keep track of the sum of integers in the window, and a constructor that initializes the window size.

The next method should take an integer as input, add it to the queue, update the sum, remove the oldest integer if the window size exceeds the queue size and calculate the average.

The implementation is as follows:

class MovingAverage:
    def __init__(self, windowSize: int):
        self.queue = []
        self.sum = 0
        self.windowSize = windowSize

    def next(self, val: int) -> float:
        # add the incoming integer to the queue
        self.queue.append(val)

        # update the sum of integers in the queue
        self.sum += val

        # remove the oldest integer if the queue size exceeds the window size
        if len(self.queue) > self.windowSize:
            oldest = self.queue.pop(0)
            self.sum -= oldest

        # calculate the average of all integers in the queue
        return self.sum / len(self.queue)

Time Complexity:

The time complexity of the solution is O(1) as the next method runs in constant time for each input integer, and we only perform basic arithmetic operations and append and pop operations on the queue.

1