Code Implementation

from collections import deque

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

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

#include <queue>

class MovingAverage {
private:
    std::queue<int> window;
    int maxSize;
    double windowSum;
public:
    MovingAverage(int size) : maxSize(size), windowSum(0) {}

    double next(int val) {
        window.push(val);
        windowSum += val;
        if (window.size() > maxSize) {
            windowSum -= window.front();
            window.pop();
        }
        return windowSum / window.size();
    }
};
      

import java.util.*;

class MovingAverage {
    private Queue<Integer> window;
    private int maxSize;
    private double windowSum;

    public MovingAverage(int size) {
        this.maxSize = size;
        this.window = new LinkedList<>();
        this.windowSum = 0;
    }

    public double next(int val) {
        window.add(val);
        windowSum += val;
        if (window.size() > maxSize) {
            windowSum -= window.poll();
        }
        return windowSum / window.size();
    }
}
      

class MovingAverage {
    constructor(size) {
        this.size = size;
        this.queue = [];
        this.windowSum = 0;
    }

    next(val) {
        this.queue.push(val);
        this.windowSum += val;
        if (this.queue.length > this.size) {
            this.windowSum -= this.queue.shift();
        }
        return this.windowSum / this.queue.length;
    }
}
      

Problem Description

The "Moving Average from Data Stream" problem asks you to design a class that calculates the moving average of the last size integers in a stream of numbers.

Specifically, you will implement a class with:

• A constructor that takes an integer size and sets the window size for the moving average.
• A method next(val) that accepts an integer val, adds it to the stream, and returns the average of the last size elements (or all elements so far if fewer than size).

• Each call to next adds a new integer to the stream.
• The moving average always uses up to the last size elements.
• There is only one valid moving average at each step; previous elements outside the window are not reused.

Thought Process

When approaching this problem, the first idea is to keep track of all numbers seen so far, and every time next is called, compute the average of the last size elements. This could be done by storing all numbers in a list or array and, for each call, slicing the last size elements to compute the sum and average.

However, this brute-force approach is inefficient because each call would require summing up to size numbers, leading to unnecessary repeated work, especially as the stream grows. To optimize, we need a way to:

• Efficiently add new numbers to our window
• Efficiently remove the oldest number when the window exceeds size
• Quickly compute the sum and average without re-summing the whole window each time

Solution Approach

To solve the problem efficiently, we use a sliding window of size size to keep track of the most recent numbers. Here’s the step-by-step strategy:

1. Initialization:
   • Store the window size (size).
   • Use a queue (or deque) to store the numbers in the current window.
   • Maintain a running sum of the numbers in the window.
2. Processing Each Number:
   • When next(val) is called, add val to the end of the queue and increase the running sum by val.
   • If the queue size exceeds size, remove the oldest element from the front and decrease the running sum by that value.
   • Compute the average as running sum / current window size.
3. Return the Result:
   • Return the computed average as a floating-point value.

Using a queue ensures that both adding and removing elements are efficient (O(1) time), and maintaining a running sum means the average can be computed quickly without iterating over the window each time.

Example Walkthrough

Let's walk through an example with size = 3 and a stream of values: [1, 10, 3, 5].

• Call next(1):
  • Window: [1]
  • Sum: 1
  • Average: 1 / 1 = 1.0
• Call next(10):
  • Window: [1, 10]
  • Sum: 11
  • Average: 11 / 2 = 5.5
• Call next(3):
  • Window: [1, 10, 3]
  • Sum: 14
  • Average: 14 / 3 ≈ 4.6667
• Call next(5):
  • Window: [10, 3, 5] (1 is removed as the window slides)
  • Sum: 18
  • Average: 18 / 3 = 6.0

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(size) per next call, because we would sum up to size elements every time.
• Space Complexity: O(N), where N is the total number of elements seen so far, since we store all elements.

• Time Complexity: O(1) per next call. Both adding/removing from the queue and updating the sum are constant time.
• Space Complexity: O(size), since we only store up to size elements in the window at any time.

The optimized approach is much more scalable, especially for large streams and small window sizes.

Summary

In summary, the "Moving Average from Data Stream" problem is elegantly solved using a sliding window with a queue (or deque) and a running sum. This approach allows us to efficiently maintain the average of the most recent size elements in constant time and space relative to the window size. The key insight is to only store what's necessary and to update the sum incrementally, avoiding unnecessary recomputation.