224. Moving Average from Data Stream

Keep the window in a queue and a running total. On each value, add it; if the window overflows, subtract the value that left. The average is total / current window size.

Slide the window with a running sum

Maintain a queue of the last size values and their total. On next(val): enqueue val, add to total; if the queue exceeds size, dequeue the oldest and subtract it. Return total / len(queue).

next(val): q.append(val); total += val
          if len(q) > size: total -= q.popleft()
          return total / len(q)

Worked example

size 3: next(1)=1.0, next(10)=5.5, next(3)=4.666..., next(5)=6.0 (window [10,3,5]).

Complexity

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

import java.util.ArrayDeque;
import java.util.Queue;

class MovingAverage {
    private int size;
    private Queue<Integer> q = new ArrayDeque<>();
    private double total = 0;

    public MovingAverage(int size) {
        this.size = size;
    }

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