Moving Average From Data Stream

1. Define the problem

Numbers arrive one at a time. After each one, report the average of the last size numbers . Before you have that many, average everything you have so far. Hold the last size numbers in a queue and also keep a running sum . When a new number arrives, add it to the back of the queue and add it to the sum. If the queue is now too long, remove the front number and subtract it from the sum. Keeping the sum as you go means you never have to add the whole window up again, so each number costs the same small amount of work.

Constraints

1 ≤ size ≤ 1000
-10⁵ ≤ value ≤ 10⁵
At most 10⁴ values arrive
The average is a decimal number, not rounded

Example

Inputsize = 3, nums = [1, 10, 3, 5]

Output[1, 5.5, 4.666666666666667, 6]

Explanation The first three averages use everything so far. At the fourth number the window is full, so 1 leaves and the average is (10 + 3 + 5) / 3 = 6.

2. Know the words first

In plain terms

Data stream: Values that arrive one after another over time. You handle each one as it comes and cannot look ahead at the values that have not arrived yet.
Running sum: A single number you keep updated as values come and go: add what enters, subtract what leaves. It saves re-adding the whole window each time.
Window size: The most recent values you are allowed to include in the average. Once the queue is longer than this, the oldest value has to go.

3. Visualize the solution

One row of cells is the queue holding the current window, front on the left

0—

1—

2—

3—

Statusinit

Window size is 3. The queue is empty and the running sum is 0.

What happens in this step

size = 3
queue = [] (all four slots empty)
sum = 0
averages = []

The fourth slot exists only so you can see the moment the queue becomes too long.

Step 1 of 7

Steps to visualize

Each arriving number goes into the first free slot on the right and is added to the running sum.
If the queue is now longer than the window size, the front number leaves and is subtracted from the sum.
The highlight frame covers the numbers currently inside the window.
The average is always the running sum divided by how many numbers are in the queue.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the queue holding the current window, front on the left

0—

1—

2—

3—

Statusinit

Window size is 3. The queue is empty and the running sum is 0.

What happens in this step

size = 3
queue = [] (all four slots empty)
sum = 0
averages = []

The fourth slot exists only so you can see the moment the queue becomes too long.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function movingAverage(size, nums) {
  const queue = [];
  const averages = [];
  let sum = 0;

  for (let i = 0; i < nums.length; i++) {
    queue.push(nums[i]);
    sum += nums[i];

    if (queue.length > size) {
      sum -= queue.shift();
    }

    averages.push(sum / queue.length);
  }

  return averages;
}

Time: O(n)
Space: O(size)

6. Test cases

Test cases

Input	Expected	Covers
`size = 3, nums = [1, 10, 3, 5]`	`[1, 5.5, 4.666666666666667, 6]`	example from the docstring
`size = 1, nums = [1, 2, 3]`	`[1, 2, 3]`	a window of one just reports each number back
`size = 2, nums = [-1, -2, -3]`	`[-1, -1.5, -2.5]`	negative numbers and a moving window
`size = 5, nums = [1, 2, 3]`	`[1, 1.5, 2]`	fewer numbers arrive than the window size
`size = 2, nums = [4, 4, 4, 4]`	`[4, 4, 4, 4]`	identical values keep the average steady
`size = 3, nums = []`	`[]`	nothing arrives at all, the degenerate case

Moving Average From Data Stream