Problem Statement

Given a stream of integers and a window size size, compute the average of the last size values each time a new value arrives.

If fewer than size values have been seen so far, compute the average of all values seen.

Implement the MovingAverage class:

• MovingAverage(int size) initializes the object with the window size.
• float next(int val) adds val to the stream and returns the average of the last size values (or all values if fewer than size have been added).

Additional information

• 1 <= size <= 1000
• -100,000 <= val <= 100,000
• At most 10,000 calls will be made to next.

Example 1:

Input:
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]

Output: [null, 1.0, 5.5, 4.66667, 6.0]

Explanation:

• MovingAverage(3) -- window size is 3
• next(1) -- stream: [1], average = 1/1 = 1.0
• next(10) -- stream: [1, 10], average = 11/2 = 5.5
• next(3) -- stream: [1, 10, 3], average = 14/3 = 4.66667
• next(5) -- stream: [10, 3, 5] (window of 3), average = 18/3 = 6.0

Example 2:

Input:
["MovingAverage", "next", "next"]
[[1], [5], [10]]

Output: [null, 5.0, 10.0]

Explanation: Window size is 1, so each call just returns the latest value.

Brute Force (Store All Values)

Intuition

Store every value that arrives. On each next call, slice the last size elements and compute their average. This is simple but recalculates the sum every time.

Algorithm

1. Maintain a list data of all values.
2. On next(val): append val. Take the last min(len(data), size) elements, sum them, and divide by the count.

class MovingAverage:
    def __init__(self, size):
        self.size = size
        self.data = []

    def next(self, val):
        self.data.append(val)
        window = self.data[-self.size:]
        return sum(window) / len(window)

Time & Space Complexity

• Time complexity: O(size) per next call

• Reason: Slicing and summing the last size elements takes O(size) time.

• Space complexity: O(n)

• Reason: We store all n values ever received, even though we only need the last size.

Queue with Running Sum (Optimal)

Intuition

Instead of recalculating the sum each time, maintain a running sum and a queue of the current window. When a new value arrives, add it to the sum. If the window exceeds size, remove the oldest value from both the queue and the sum. The average is always sum / queue.length.

Algorithm

1. Maintain a deque (queue) and a window_sum.
2. On next(val):
   • Append val to the queue and add it to window_sum.
   • If the queue length exceeds size, pop the front element and subtract it from window_sum.
   • Return window_sum / len(queue).

from collections import deque

class MovingAverage:
    def __init__(self, size):
        self.size = size
        self.queue = deque()
        self.window_sum = 0

    def next(self, val):
        self.queue.append(val)
        self.window_sum += val
        if len(self.queue) > self.size:
            self.window_sum -= self.queue.popleft()
        return self.window_sum / len(self.queue)

Time & Space Complexity

• Time complexity: O(1) per next call

• Reason: Appending, popping, and arithmetic are all O(1) operations.

• Space complexity: O(size)

• Reason: The queue holds at most size elements.