Moving Average from Data Stream

easy queue design sliding window

Problem

Given a window size size, design a class that returns the moving average of the last size values from a number stream.

Inputsize = 3, stream = [1, 10, 3, 5]

Output[1.0, 5.5, 4.67, 6.0]

Keep a queue of the last 3 values plus a running sum.

window

stream

from collections import deque

class MovingAverage:
    def __init__(self, size):
        self.size = size
        self.q = deque()
        self.s = 0
    def next(self, val):
        self.q.append(val)
        self.s += val
        if len(self.q) > self.size:
            self.s -= self.q.popleft()
        return self.s / len(self.q)

class MovingAverage {
  constructor(size) { this.size = size; this.q = []; this.s = 0; }
  next(val) {
    this.q.push(val);
    this.s += val;
    if (this.q.length > this.size) this.s -= this.q.shift();
    return this.s / this.q.length;
  }
}

class MovingAverage {
    private Deque<Integer> q = new ArrayDeque<>();
    private int size; private double sum = 0;
    public MovingAverage(int size) { this.size = size; }
    public double next(int val) {
        q.offer(val); sum += val;
        if (q.size() > size) sum -= q.poll();
        return sum / q.size();
    }
}

class MovingAverage {
    queue<int> q;
    int size; double sum = 0;
public:
    MovingAverage(int size) : size(size) {}
    double next(int val) {
        q.push(val); sum += val;
        if ((int)q.size() > size) { sum -= q.front(); q.pop(); }
        return sum / q.size();
    }
};

Explanation

The naive way to get a moving average would be to add up the last few numbers every single time. That repeats the same additions over and over. Instead, we keep a running sum and adjust it incrementally, so each call is constant time.

We hold the current window in a queue and a variable s for the sum of everything in that queue. On next(val) we push val onto the back and add it to s.

If the queue now holds more than size items, the window has overflowed, so we pop the oldest item from the front and subtract it from s. The queue and sum always describe exactly the last size values.

The answer is simply s / len(q) — the sum divided by how many numbers are currently in the window.

Example with size = 3 and stream 1, 10, 3, 5: after 1 the average is 1.0; after 10 it is (1+10)/2 = 5.5; after 3 it is (1+10+3)/3 ≈ 4.67; after 5 we drop 1 and get (10+3+5)/3 = 6.0.

Time: O(1) per call Space: O(size)