0346.md

346. Moving Average from Data Stream

Level:

Topic:

Question

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Intuition

Maintain a queue and add value to queue when calling next().

• when queue size is greater than the input size, remove the first in queue and subtract from the current window sum
• divide the current sum by the queue size

Code

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

class MovingAverage {
    Queue<Integer> q;
    int size;
    double sum;

    public MovingAverage(int size) {
        this.q = new LinkedList<>();
        this.size = size;
        this.sum = 0.0;
    }

    public double next(int val) {
        sum += val;
        q.add(val);

        if (q.size() > size)
            sum -= q.poll();
        return sum/q.size();
    }
}