Moving Average from Data Stream
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 received so far. Once the window holds size values, each new value pushes the oldest one out. The problem reduces to tracking which values are currently in the window and computing their average efficiently.
The values enter the window in arrival order and leave in that same order: the oldest value is always the first to be evicted. A structure that supports adding to one end and removing from the other (first-in, first-out) fits this directly.
Key Constraints:
1 <= size <= 1000→ The window holds at most 1000 values, so an O(size) recomputation per call is cheap. A running sum still improves this to O(1).-10^5 <= val <= 10^5→ Values can be negative, so the running sum is signed. With at most 1000 values in the window and magnitudes up to 10^5, the sum stays within +/- 10^8, well inside a 32-bit integer and exactly representable in a double.- At most
10^4calls tonext→ An O(size) approach costs about 10^7 operations across all calls, which is acceptable, but the running-sum approaches below avoid the per-call loop entirely.
Approach 1: Brute Force (Store All Values)
Intuition
Store every value that arrives in a list. When asked for the average, take the last size values in the list and compute their average from scratch.
This works but does redundant work. It keeps all historical values even though only the last size of them matter. It also recomputes the sum on every next call, even though at most one value in the window changed since the previous call.
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. The next approach keeps a running sum and adjusts it incrementally as elements enter and leave the window.
Approach 2: Queue with Running Sum
Intuition
Instead of recomputing the sum from scratch, maintain a running sum. When a new value arrives, add it to the sum. If the window is already full, also subtract the oldest value. Each next call then does a fixed amount of work regardless of window size.
A queue holds the window. Values enter from the back (enqueue) and leave from the front (dequeue), matching the order in which the window admits and evicts values. Pairing the queue with a running sum, the average is sum / queue.size().
The invariant is that sum always equals the total of the values currently in the queue. It holds on initialization (empty queue, sum zero) and is preserved by each next call: adding val updates both the queue and the sum together, and evicting the front element subtracts exactly that element. Because the queue is FIFO, the front is always the oldest value, so the element removed when the window overflows is the correct one to drop.
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 allocates and frees nodes (or shifts a dynamic array) as values enter and leave. The next approach pre-allocates a fixed array of size slots and reuses them through a circular write pointer, avoiding that per-call allocation.
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.