Moving Average from Data Stream
Last Updated: April 3, 2026
Understanding the Problem
We need to design a class that maintains a sliding window of the most recent size values from a data stream. Every time a new value arrives via the next method, we return the average of the values currently in the window.
The window behaves like a fixed-capacity container. When we have fewer values than size, we average everything we have so far. Once we hit size values, each new value pushes the oldest one out. So the real question here is: how do we efficiently track which values are in the window and compute their average?
The key observation is that we need a data structure that supports adding to one end and removing from the other, which is exactly what a queue does.
Key Constraints:
1 <= size <= 1000→ The window is small, so even storing all values in a list and recalculating every time would be fast enough. But a queue-based approach is cleaner.-10^5 <= val <= 10^5→ Values can be negative. With up to 10^4 calls and values up to 10^5, the running sum can reach 10^9, which fits in a 32-bit integer. No overflow concerns with standard int/double types.- At most
10^4calls tonext→ Even an O(size) approach per call would mean 10^7 operations at worst. That's fine. But we can do O(1) per call with a running sum.
Approach 1: Brute Force (Store All Values)
Intuition
The simplest approach: store every value that arrives in a list. When asked for the average, look at the last size values in the list and compute their average from scratch.
This is straightforward but wasteful. We keep all historical values even though we only need the last size of them. And we recompute the sum every time next is called, even though most of the values in the window haven't changed.
Algorithm
- Initialize an empty list to store all incoming values.
- On each
next(val)call, appendvalto the list. - Determine the start index of the window:
max(0, list.size() - size). - Sum all values from the start index to the end of the list.
- Return the sum divided by the number of values in the window.
Example Walkthrough
Input: size = 3, calls: next(1), next(10), next(3), next(5)
After next(1): values = [1], window = [1], average = 1.0
After next(10): values = [1, 10], window = [1, 10], average = 5.5
After next(3): values = [1, 10, 3], window = [1, 10, 3], average = 4.67
After next(5): values = [1, 10, 3, 5], window = last 3 = [10, 3, 5], average = 6.0
Code
- Time Complexity: O(size) per
nextcall. Each call sums up tosizeelements. Over n total calls, that's O(n * size) total work. - Space Complexity: O(n) where n is the total number of
nextcalls. We store every value ever received, even ones that have fallen out of the window.
Every next call recomputes the sum by iterating over up to size elements, even though only one value changed. What if we maintained a running sum and just adjusted it when an element enters or leaves the window?
Approach 2: Queue with Running Sum
Intuition
Instead of recalculating the sum from scratch, we maintain a running sum. When a new value arrives, we add it to the sum. If the window is already full, we also remove the oldest value from the sum. This way each next call does O(1) work.
The natural data structure for this is a queue. Values enter from one end (enqueue) and leave from the other (dequeue), which is exactly how a sliding window works. We pair the queue with a running sum variable, and the average is just sum / queue.size().
The moving average only changes in two ways when a new value arrives: the new value enters the window, and (if the window was already full) the oldest value leaves. Instead of recalculating the entire sum, we adjust it by adding the new value and subtracting the old one. This is the incremental computation pattern, and it reduces each operation from O(size) to O(1).
The queue naturally enforces the FIFO order. The element at the front is always the oldest, so when we need to evict, we just dequeue. The running sum stays perfectly in sync because we add on enqueue and subtract on dequeue.
Algorithm
- Initialize a queue (or deque) and a running sum variable, both empty/zero.
- On each
next(val)call: - Add
valto the queue and addvalto the running sum. - If the queue size exceeds the window size, dequeue the oldest value and subtract it from the running sum.
- Return the running sum divided by the current queue size.
Example Walkthrough
Code
- Time Complexity: O(1) per
nextcall. Each call does a constant number of operations: one enqueue, possibly one dequeue, one addition, possibly one subtraction, and one division. - Space Complexity: O(size). The queue holds at most
sizeelements at any time. Unlike Approach 1, we don't store historical values that have left the window.
The queue approach is clean, but it uses a linked list or dynamic array with shift operations. What if we pre-allocated a fixed-size array and reused slots with a circular pointer?
Approach 3: Circular Buffer with Running Sum
Intuition
We can avoid dynamic memory entirely by using a fixed-size circular buffer. Allocate an array of exactly size slots. Keep a write pointer that moves forward with each new value, wrapping around to 0 when it reaches the end. Before overwriting a slot, subtract the old value from the running sum. Then write the new value and add it to the sum.
The buffer is initialized to zeros. Before the buffer is full, subtracting buffer[ptr] subtracts zero, which is harmless. Once the buffer is full, buffer[ptr] holds the oldest value, which is exactly what we need to remove. This eliminates the need for an explicit "is the buffer full?" check for the subtraction logic.
Algorithm
- Initialize a fixed-size array of
sizeslots (all zeros), a write pointer at 0, a running sum at 0, and a count of values seen so far. - On each
next(val)call: - Subtract the value at the current write position from the running sum.
- Write
valto the current position and add it to the running sum. - Advance the write pointer:
pointer = (pointer + 1) % size. - Increment the count (capped at
size). - Return the running sum divided by the current count.
Example Walkthrough
Code
- Time Complexity: O(1) per
nextcall. Each call does a constant number of arithmetic operations and one array access. No loops, no dynamic allocation. - Space Complexity: O(size). We allocate exactly
sizeslots, no more. Unlike the queue approach, there's no linked list node overhead or dynamic resizing.