346. Moving Average from Data Stream 🔒

Description

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 size.
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
-10⁵ <= val <= 10⁵
At most 10⁴ calls will be made to next.

Solutions

Solution 1: Circular Array

We define a variable \(\textit{s}\) to calculate the sum of the last \(\textit{size}\) elements, and a variable \(\textit{cnt}\) to record the total number of current elements. Additionally, we use an array \(\textit{data}\) of length \(\textit{size}\) to record the value of each element at each position.

When calling the \(\textit{next}\) function, we first calculate the index \(i\) where \(\textit{val}\) should be stored, then update the sum \(s\), set the value at index \(i\) to \(\textit{val}\), and increment the element count by one. Finally, we return the value of \(\frac{s}{\min(\textit{cnt}, \textit{size})}\).

The time complexity is \(O(1)\), and the space complexity is \(O(n)\), where \(n\) is the integer \(\textit{size}\) given in the problem.

Python3JavaC++GoTypeScript

class MovingAverage:

    def __init__(self, size: int):
        self.s = 0
        self.data = [0] * size
        self.cnt = 0

    def next(self, val: int) -> float:
        i = self.cnt % len(self.data)
        self.s += val - self.data[i]
        self.data[i] = val
        self.cnt += 1
        return self.s / min(self.cnt, len(self.data))


# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

class MovingAverage {
    private int s;
    private int cnt;
    private int[] data;

    public MovingAverage(int size) {
        data = new int[size];
    }

    public double next(int val) {
        int i = cnt % data.length;
        s += val - data[i];
        data[i] = val;
        ++cnt;
        return s * 1.0 / Math.min(cnt, data.length);
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

class MovingAverage {
public:
    MovingAverage(int size) {
        data.resize(size);
    }

    double next(int val) {
        int i = cnt % data.size();
        s += val - data[i];
        data[i] = val;
        ++cnt;
        return s * 1.0 / min(cnt, (int) data.size());
    }

private:
    int s = 0;
    int cnt = 0;
    vector<int> data;
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

type MovingAverage struct {
    s    int
    cnt  int
    data []int
}

func Constructor(size int) MovingAverage {
    return MovingAverage{
        data: make([]int, size),
    }
}

func (this *MovingAverage) Next(val int) float64 {
    i := this.cnt % len(this.data)
    this.s += val - this.data[i]
    this.data[i] = val
    this.cnt++
    return float64(this.s) / float64(min(this.cnt, len(this.data)))
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * obj := Constructor(size);
 * param_1 := obj.Next(val);
 */

class MovingAverage {
    private s: number = 0;
    private cnt: number = 0;
    private data: number[];

    constructor(size: number) {
        this.data = Array(size).fill(0);
    }

    next(val: number): number {
        const i = this.cnt % this.data.length;
        this.s += val - this.data[i];
        this.data[i] = val;
        this.cnt++;
        return this.s / Math.min(this.cnt, this.data.length);
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * var obj = new MovingAverage(size)
 * var param_1 = obj.next(val)
 */

Solution 2: Queue

We can use a queue \(\textit{q}\) to store the last \(\textit{size}\) elements, and a variable \(\textit{s}\) to record the sum of these \(\textit{size}\) elements.

When calling the \(\textit{next}\) function, we first check if the length of the queue \(\textit{q}\) is equal to \(\textit{size}\). If it is, we dequeue the front element of the queue \(\textit{q}\) and update the value of \(\textit{s}\). Then we enqueue \(\textit{val}\) and update the value of \(\textit{s}\). Finally, we return the value of \(\frac{s}{\text{len}(q)}\).