DSA problem
Moving Average from Data Stream
Design a data structure that calculates the moving average of all integers in a sliding window of a given size. You are given an integer size for the fixed window length. Implement the MovingAverage class:
MovingAverage(int size) constructs the data structure with the specified window size. double next(int val) returns the moving average of the last size values of the stream; if fewer than size numbers have arrived so far, return the average of all numbers seen.
A naive implementation would keep every number in an array and recompute the average by summing the last size elements on every call, costing O(size) time per query. That is unnecessarily slow when the stream is long.
The optimal design uses a fixed-size FIFO queue and a running sum. When a new value arrives, push it to the back of the queue and add it to the sum; if the queue size now exceeds size, pop the front element and subtract it from the sum. The current average is sum / queue.size(). Every operation does a constant amount of work, so each next call runs in O(1) time with O(size) extra space — proportional only to the window length, not the length of the stream.
Examples
["MovingAverage","next","next","next","next"]
[[3],[1],[10],[3],[5]][null,1.0,5.5,4.66667,6.0]["MovingAverage","next","next"]
[[1],[4],[7]][null,4.0,7.0]["MovingAverage","next","next","next"]
[[5],[2],[2],[2]][null,2.0,2.0,2.0]Constraints
- 1 <= size <= 1000
- -10^5 <= val <= 10^5
- At most 10^4 calls will be made to next.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.