346. Moving Average from Data Stream - Detailed Explanation

Problem Statement

Implement a class MovingAverage that calculates the moving average of the last size elements from a stream of integers. The class should support two operations:

• MovingAverage(int size): Constructor to initialize the object with the window size.
• double next(int val): Returns the moving average of the last size values of the data stream (including the new value val).

Example Test Cases

Example 1:

MovingAverage obj = new MovingAverage(3);
obj.next(1);   // returns 1.0
obj.next(10);  // returns (1 + 10) / 2 = 5.5
obj.next(3);   // returns (1 + 10 + 3) / 3 = 4.67
obj.next(5);   // returns (10 + 3 + 5) / 3 = 6.0

Example 2:

MovingAverage obj = new MovingAverage(2);
obj.next(5);   // returns 5.0
obj.next(15);  // returns (5 + 15) / 2 = 10.0
obj.next(10);  // returns (15 + 10) / 2 = 12.5

Hints to Solve

1. Use a data structure to store the last size values and allow easy addition/removal of elements.
2. Maintain a running sum so you can compute the new average quickly without summing all elements from scratch each time.

Approaches

Brute Force Approach (Using an Array/List)

• Keep a list of all values seen so far.
• On each call to next(val), add the new value to the list and then compute the sum of the last size elements in the list.
• Return the average as this sum divided by size (or by the number of elements if fewer than size have been seen so far).
• Time Complexity: O(size) per query (each next call requires iterating over up to size elements for the sum).

Optimized Approach (Using a Queue – Sliding Window)

• Use a queue (or deque) to store the most recent size values. This naturally discards the oldest value when the size is exceeded.
• Maintain a running sum of the values in the queue (the current window sum).
• On each next(val) call:
  • If the queue is already at the maximum size, remove (popleft()/poll()) the oldest value and subtract it from the running sum.
  • Add the new value to the queue and add it to the running sum.
  • Compute the average as running_sum / current_window_length.
• Time Complexity: O(1) per query (each next operation does a constant amount of work, regardless of the window size).

Code Implementations

Python Solution (Queue Approach)