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.
We define a variable s to calculate the sum of the last size elements, and a variable cnt to record the total number of current elements. Additionally, we use an array data of length size to record the value of each element at each position.
When calling the next function, we first calculate the index i where val should be stored, then update the sum s, set the value at index i to val, and increment the element count by one. Finally, we return the value of \frac{s}{min(cnt, size)}.
The time complexity is O(1), and the space complexity is O(n), where n is the integer size given in the problem.
Python
Java
C++
Go
TypeScript
We can use a queue q to store the last size elements, and a variable s to record the sum of these size elements.
When calling the next function, we first check if the length of the queue q is equal to size. If it is, we dequeue the front element of the queue q and update the value of s. Then we enqueue val and update the value of s. Finally, we return the value of \frac{s}{len(q)}.
The time complexity is O(1), and the space complexity is O(n), where n is the integer size given in the problem.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Circular Array | — |
| Queue | — |
| 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 |
Moving Average from Data Stream || Leetcode 346 || 1 Variant Question Big Tech Actually Asks • Coding with Minmer • 7,956 views views
Watch 9 more video solutions →Practice Moving Average from Data Stream with our built-in code editor and test cases.
Practice on FleetCode