Problem Description

You need to implement a class that calculates the moving average of a stream of integers within a sliding window of a fixed size.

The MovingAverage class should support two operations:

1. Constructor MovingAverage(int size): Initializes the object with a window size. This window will hold at most size recent values from the stream.

2. Method next(int val): Adds a new integer val to the stream and returns the average of the most recent values in the window. If the total number of values seen so far is less than the window size, it returns the average of all values seen so far.

For example, if the window size is 3:

• After adding the first value, the average is just that value
• After adding the second value, the average is of those two values
• After adding the third value, the average is of all three values
• After adding the fourth value, the window slides - it drops the first value and keeps only the most recent three values, then calculates their average

The solution uses a circular array approach where:

• self.s maintains the sum of values currently in the window
• self.data is a fixed-size array that stores the window values
• self.cnt tracks the total number of values processed
• When a new value arrives, it replaces the oldest value in the circular array at position cnt % size, and the sum is updated by adding the new value and subtracting the old value at that position
• The average is calculated by dividing the sum by the minimum of cnt and size (to handle cases where fewer than size elements have been added)

Intuition

The key insight is that we need to efficiently maintain a sliding window of the most recent values and calculate their average. The naive approach would be to store all values in a queue, remove the oldest when the window is full, and recalculate the sum each time. However, this would require iterating through all window elements to compute the sum for each new value.

We can optimize this by recognizing that when the window slides, only two values change: one value leaves the window and one enters. Instead of recalculating the entire sum, we can maintain a running sum and simply update it by subtracting the leaving value and adding the entering value. This gives us O(1) time complexity for each operation.

The circular array technique comes from observing that we don't need to physically shift elements when the window slides. Since we always replace the oldest value with the newest one, we can treat our fixed-size array as circular. By using the modulo operator cnt % size, we can map any count to a position in our array. When cnt exceeds the array size, the index wraps around to the beginning, naturally overwriting the oldest values.

For example, with a window size of 3:

• Position 0 stores the 1st, 4th, 7th, ... values
• Position 1 stores the 2nd, 5th, 8th, ... values
• Position 2 stores the 3rd, 6th, 9th, ... values

This pattern ensures that at any point, our array contains exactly the most recent min(cnt, size) values. By maintaining the sum incrementally with s += val - data[i], we avoid the need to traverse the array, making each update operation constant time.

Solution Approach

The solution implements a circular array to efficiently maintain a sliding window of values. Here's how each component works:

Data Structure Setup:

• self.s: Maintains the running sum of all values currently in the window
• self.data: A fixed-size array of length size that stores the window values
• self.cnt: Counts the total number of values processed (not limited to window size)

Initialization (__init__ method):

def __init__(self, size: int):
    self.s = 0                  # Sum starts at 0
    self.data = [0] * size      # Pre-allocate array with zeros
    self.cnt = 0                # No values processed yet

Adding Values (next method):

1. Calculate the circular index:

   i = self.cnt % len(self.data)

   This maps the current count to a position in the array. For example, if size=3 and cnt=5, then i = 5 % 3 = 2, so the new value goes to position 2, replacing whatever was there before.

2. Update the running sum:

   self.s += val - self.data[i]

   Before overwriting the old value at position i, we adjust the sum by removing the old value (self.data[i]) and adding the new value (val). This maintains the correct sum in constant time.

3. Store the new value:

   self.data[i] = val

   Replace the old value at position i with the new value.

4. Increment the counter:

   self.cnt += 1

   Track that we've processed one more value.

5. Calculate and return the average:

   return self.s / min(self.cnt, len(self.data))

   The divisor is min(self.cnt, len(self.data)) to handle two cases:

   • When cnt < size: We haven't filled the window yet, so divide by cnt
   • When cnt >= size: The window is full, so divide by size

Time Complexity: O(1) for each next operation since we only perform constant-time operations.

Space Complexity: O(size) for storing the window values in the array.

Example Walkthrough

Let's walk through an example with window size 3 and the sequence of values: 1, 10, 3, 5.

Initial State:

• size = 3
• s = 0 (running sum)
• data = [0, 0, 0] (circular array)
• cnt = 0 (values processed)

Step 1: next(1)

• Calculate index: i = 0 % 3 = 0
• Update sum: s = 0 + 1 - 0 = 1 (add new value 1, subtract old value at data[0] which is 0)
• Store value: data[0] = 1, so data = [1, 0, 0]
• Increment counter: cnt = 1
• Calculate average: 1 / min(1, 3) = 1 / 1 = 1.0
• Window contains: [1]

Step 2: next(10)

• Calculate index: i = 1 % 3 = 1
• Update sum: s = 1 + 10 - 0 = 11 (add new value 10, subtract old value at data[1] which is 0)
• Store value: data[1] = 10, so data = [1, 10, 0]
• Increment counter: cnt = 2
• Calculate average: 11 / min(2, 3) = 11 / 2 = 5.5
• Window contains: [1, 10]

Step 3: next(3)

• Calculate index: i = 2 % 3 = 2
• Update sum: s = 11 + 3 - 0 = 14 (add new value 3, subtract old value at data[2] which is 0)
• Store value: data[2] = 3, so data = [1, 10, 3]
• Increment counter: cnt = 3
• Calculate average: 14 / min(3, 3) = 14 / 3 ≈ 4.67
• Window contains: [1, 10, 3] (window is now full)

Step 4: next(5)

• Calculate index: i = 3 % 3 = 0 (wraps around to beginning!)
• Update sum: s = 14 + 5 - 1 = 18 (add new value 5, subtract old value at data[0] which is 1)
• Store value: data[0] = 5, so data = [5, 10, 3]
• Increment counter: cnt = 4
• Calculate average: 18 / min(4, 3) = 18 / 3 = 6.0
• Window contains: [10, 3, 5] (value 1 was replaced by 5)

Notice how in Step 4, the index wrapped around to 0, replacing the oldest value (1) with the newest value (5). The sum was efficiently updated by subtracting the old value and adding the new one, avoiding the need to recalculate the entire sum. The circular array ensures we always maintain exactly the most recent 3 values without shifting any elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The next method performs a constant number of operations:

• Calculating the index i using modulo operation: O(1)
• Updating the sum s by subtracting the old value and adding the new value: O(1)
• Updating the array at index i: O(1)
• Incrementing the counter: O(1)
• Calculating and returning the average using division and min operation: O(1)

All operations are constant time, making the overall time complexity O(1) per call to next.

Space Complexity: O(n)

Where n is the size parameter passed to the constructor:

• The data array is initialized with size elements, requiring O(size) space
• The other instance variables (s, cnt) use O(1) space
• Total space complexity is O(size) = O(n)

The implementation uses a circular buffer approach where old values are overwritten once the buffer is full, maintaining a fixed space usage regardless of how many times next is called.

Common Pitfalls

1. Integer Division Instead of Float Division

A common mistake is forgetting that in some programming languages (like Python 2 or C++), dividing two integers performs integer division, truncating the decimal part.

Incorrect approach:

# In Python 2 or when using // operator
return self.window_sum // min(self.count, len(self.window))  # Wrong! Truncates decimal

Solution: Ensure you're using float division. In Python 3, the / operator automatically performs float division. In other languages, cast one operand to float:

# Python 3 (correct)
return self.window_sum / min(self.count, len(self.window))

# For languages requiring explicit casting
return float(self.window_sum) / min(self.count, len(self.window))

2. Incorrectly Handling the Initial Window Fill

Many implementations fail when the number of elements seen is less than the window size, dividing by the window size instead of the actual count.

Incorrect approach:

def next(self, val: int) -> float:
    index = self.count % len(self.window)
    self.window_sum += val - self.window[index]
    self.window[index] = val
    self.count += 1
    return self.window_sum / len(self.window)  # Wrong! Always divides by window size

Solution: Always use min(self.count, len(self.window)) as the divisor to handle both cases correctly.

3. Forgetting to Update the Sum Before Overwriting

A critical error is overwriting the old value in the circular buffer before subtracting it from the running sum.

Incorrect approach:

def next(self, val: int) -> float:
    index = self.count % len(self.window)
    self.window[index] = val  # Overwrites old value first!
    self.window_sum += val - self.window[index]  # Now subtracts the NEW value
    self.count += 1
    return self.window_sum / min(self.count, len(self.window))

Solution: Always update the sum BEFORE overwriting the old value:

self.window_sum += val - self.window[index]  # Subtract old value first
self.window[index] = val  # Then overwrite

4. Not Handling Edge Case of Size 0

If the window size is 0, the code will crash with division by zero or array allocation issues.

Solution: Add validation in the constructor:

def __init__(self, size: int):
    if size <= 0:
        raise ValueError("Window size must be positive")
    self.window_sum = 0
    self.window = [0] * size
    self.count = 0

5. Using a Queue Instead of Circular Array

While using a queue (deque) works correctly, it's less efficient for this specific problem.

Less optimal approach:

from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.queue = deque(maxlen=size)
  
    def next(self, val: int) -> float:
        self.queue.append(val)
        return sum(self.queue) / len(self.queue)  # O(n) operation!

Why circular array is better: The circular array approach maintains a running sum, achieving O(1) time complexity for each operation, while the queue approach requires O(n) time to calculate the sum each time.