Watch 10 video solutions for Moving Average from Data Stream, a easy level problem involving Array, Design, Queue. This walkthrough by NeetCode has 219,763 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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-105 <= val <= 105104 calls will be made to next.Problem Overview: Design a data structure that receives numbers from a stream and returns the moving average of the last k values. Each call to next(val) should add the new number and return the current average of the most recent window.
Approach 1: Queue with Running Sum (Time: O(1) per operation, Space: O(k))
Use a queue to keep the last k elements from the stream. Maintain a running sum of elements currently in the queue. When a new value arrives, push it to the queue and add it to the sum. If the queue size exceeds k, remove the oldest value and subtract it from the sum. The moving average is simply sum / queue.size(). Each update performs constant-time enqueue/dequeue operations, making it efficient for continuous streams.
Approach 2: Circular Array (Time: O(1) per operation, Space: O(k))
Instead of a dynamic queue, store the last k values in a fixed-size circular buffer using an array. Maintain an index that rotates using index % k. When inserting a new value, subtract the value currently stored at that index from the running sum, overwrite it with the new value, then add the new value to the sum. This keeps the window size fixed while avoiding queue allocations. The average is computed using the running sum divided by the number of inserted elements (or k once the buffer is full).
Both implementations follow the same key idea: keep only the last k elements and maintain a running sum so you never recompute totals from scratch. This pattern is common in design problems and streaming systems where values arrive continuously.
Recommended for interviews: The queue-based implementation is usually the most intuitive and easiest to explain. It clearly models the sliding window of the last k values. The circular array approach shows stronger understanding of memory-efficient data structures and often performs slightly better due to fixed allocation. Interviewers typically expect the O(1) running-sum optimization rather than recomputing the average each time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Queue with Running Sum | O(1) per next() | O(k) | Most intuitive implementation for sliding window over a data stream |
| Circular Array (Ring Buffer) | O(1) per next() | O(k) | When you want fixed memory usage and fewer dynamic allocations |