Skip to main content
Talentd

Moving Average from Data Stream - Solution & Explanation

EasyPremiumFree on FleetCodeArrayDesignQueueData Stream12 min readAsked at: Amazon, Microsoft, Apple +8
Practice this problem

Problem Statement

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 <= 105
  • At most 104 calls will be made to next.

Approach Overview

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 1: Circular Array

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: Queue

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Circular Array—
Queue—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Queue with Running SumO(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

Video Solution

Moving Average from Data Stream • Kevin Naughton Jr. • 32,187 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Moving Average from Data Stream easy or hard?
Moving Average from Data Stream is classified as an Easy problem. The main idea is maintaining a sliding window of the last k elements and updating a running sum so the average can be computed in O(1) time.
Moving Average from Data Stream Python/Java solution
Python and Java implementations usually use a queue (collections.deque in Python or ArrayDeque in Java) with a running sum variable. Another common approach uses a fixed-size array as a circular buffer to overwrite old values while updating the sum.
How to solve Moving Average from Data Stream in O(1)?
Maintain a sliding window of size k and track the running sum. When a new value arrives, add it to the sum and remove the oldest value if the window exceeds k. Compute the average as sum divided by the current window size. Using a queue or circular array ensures constant-time updates.
What is the best approach for Moving Average from Data Stream?
The best approach keeps a running sum of the last k elements while storing them in a queue or circular buffer. Each new value updates the sum and removes the oldest element if the window exceeds k. This gives O(1) time per operation and O(k) space.
Is Moving Average from Data Stream asked at Google/Amazon/Meta?
Moving Average from Data Stream represents a common streaming and sliding window design pattern. Variations of this problem appear in interviews at companies like Amazon, Google, and other large tech firms when testing data stream handling and queue-based design.
What data structure is used in Moving Average from Data Stream?
The typical data structures are a queue or a circular array (ring buffer). Both store the last k elements while a running sum tracks their total, allowing the moving average to be calculated in constant time.
What is the time complexity of Moving Average from Data Stream?
The optimal solution runs in O(1) time for each next(val) call. Each update only adds the new value, optionally removes the oldest value, and computes the average using a maintained running sum.

Ready to solve this problem?

Practice Moving Average from Data Stream with our built-in code editor and test cases.

Practice on FleetCode
Previous

K Radius Subarray Averages