Moving Average from Data Stream

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

Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window.
• double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

Input [“MovingAverage”, “next”, “next”, “next”, “next”] [[3], [1], [10], [3], [5]]

Output [null, 1.0, 5.5, 4.66667, 6.0]

Explanation MovingAverage movingAverage = new MovingAverage(3); movingAverage.next(1); // return 1.0 = 1 / 1 movingAverage.next(10); // return 5.5 = (1 + 10) / 2 movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3 movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

Constraints:

• 1 <= size <= 1000
• -105 <= val <= 105
• At most 104 calls will be made to next.

Approach: Sliding Window with Queue (Optimal Solution)

Algorithm

1. Use a queue to store the elements currently in the window
2. Maintain a running sum of all elements in the queue
3. next(val): add val to the queue and the sum
4. If the queue exceeds size, remove the oldest element from the queue and subtract it from the sum
5. Return sum / queue.size()

Key Insight

Instead of recomputing the sum each time, we maintain a running sum. When the window is full, each new element replaces the oldest one, so we only need to add the new value and subtract the evicted one — both O(1).

Time & Space Complexity

• Time Complexity: O(1) per call to next
• Space Complexity: O(n) - queue stores at most size elements

Java Implementation

import java.util.LinkedList;
import java.util.Queue;

public class MovingAverage {

    private Queue<Integer> queue;
    private int capacity;
    private double sum;

    /** Initialize the object with the size of the window. */
    public MovingAverage(int size) {
        this.queue = new LinkedList<>();
        this.capacity = size;
        this.sum = 0;
    }

    /** Return the moving average of the last size values. */
    public double next(int val) {
        queue.offer(val);
        sum += val;

        // Evict the oldest element if the window is full
        if (queue.size() > capacity) {
            sum -= queue.poll();
        }

        return sum / queue.size();
    }

    // Test method
    public static void main(String[] args) {
        MovingAverage movingAverage = new MovingAverage(3);
        System.out.println("next(1): " + movingAverage.next(1));   // Expected: 1.0
        System.out.println("next(10): " + movingAverage.next(10)); // Expected: 5.5
        System.out.println("next(3): " + movingAverage.next(3));   // Expected: 4.66667
        System.out.println("next(5): " + movingAverage.next(5));   // Expected: 6.0
    }
}

Example Walkthrough

For size = 3:

1. next(1): queue=[1], sum=1, avg=1/1=1.0
2. next(10): queue=[1,10], sum=11, avg=11/2=5.5
3. next(3): queue=[1,10,3], sum=14, avg=14/3≈4.67
4. next(5): queue=[1,10,3,5], size>3, evict 1. queue=[10,3,5], sum=14-1+5=18, avg=18/3=6.0

Alternative Approach: Circular Array

public class MovingAverageArray {
    private int[] window;
    private int count;
    private int sum;
    private int head;

    public MovingAverageArray(int size) {
        this.window = new int[size];
        this.count = 0;
        this.sum = 0;
        this.head = 0;
    }

    public double next(int val) {
        count++;
        int tail = (head + 1) % window.length;
        sum += val;
        if (count > window.length) {
            sum -= window[tail];
        } else {
            head = (head + 1) % window.length;
        }
        window[tail] = val;
        return (double) sum / Math.min(count, window.length);
    }
}

The circular array variant uses fixed O(size) space without a dynamic queue, with the same O(1) time per call.

Key Insights

1. Running Sum: Avoids recomputing the average by maintaining a running total
2. Queue FIFO: The queue naturally enforces the window, evicting the oldest element first
3. Constant Time: Each next call performs O(1) work regardless of window size
4. Fractional Result: Returns a double, so the average handles partial windows correctly

The queue-based sliding window approach is the optimal solution, providing O(1) time per operation.