Moving average of a stream

Scenario

A live video page shows how many viewers are watching. A counter reports the viewer count once a minute, and a chart beside it shows a moving average, so one small spike does not make the line jump.

For each report, the chart needs the average of the last k reports. Early in a show, fewer than k reports exist, so it uses all of them. A show can send up to 100,000 reports.

Your task

Write moving_averages(counts, k).

counts is a list of viewer counts, one for each minute, oldest first.
k is how many of the latest reports to average.
After each report, find the average of the last k reports, or of all reports so far when fewer than k exist. Round it down to a whole number.
Return the list of these averages, one for each report, in order.

Examples

Example 1 (traced)#

text2 lines

Input:  counts = [10, 20, 30, 40], k = 2
Output: [10, 15, 25, 35]

Step	Report	Window (front to back)	Sum	Average
1	`10`	`10`	10	10
2	`20`	`10` `20`	30	15
3	`30`	`20` `30` (the `10` left)	50	25
4	`40`	`30` `40` (the `20` left)	70	35

The last report joins the window and the oldest one leaves, so the window slides one step at a time.

Example 2#

text2 lines

Input:  counts = [7], k = 3
Output: [7]

Only one report exists, so the average is that report.

Example 3#

text2 lines

Input:  counts = [5, 6, 6, 5], k = 10
Output: [5, 5, 5, 5]

Fewer than k reports exist at every step, so each average uses all of them: 5, then 11 / 2 rounded down, then 17 / 3, then 22 / 4.

Constraints

1 ≤ length of counts ≤ 10^5
0 ≤ counts[i] ≤ 10^6
1 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

A plan that adds up the last k reports again for every report costs about n times k steps. With n and k both near 10^5, that is 10^10, which is too slow.

So keep a running sum. When one report arrives and one leaves, the sum changes by two numbers, and no re-adding is needed.

Scenario

A live video page shows how many viewers are watching. A counter reports the viewer count once a minute, and a chart beside it shows a moving average, so one small spike does not make the line jump.

For each report, the chart needs the average of the last k reports. Early in a show, fewer than k reports exist, so it uses all of them. A show can send up to 100,000 reports.

Your task

Write moving_averages(counts, k).

counts is a list of viewer counts, one for each minute, oldest first.
k is how many of the latest reports to average.
After each report, find the average of the last k reports, or of all reports so far when fewer than k exist. Round it down to a whole number.
Return the list of these averages, one for each report, in order.

Examples

Example 1 (traced)#

text2 lines

Input:  counts = [10, 20, 30, 40], k = 2
Output: [10, 15, 25, 35]

Step	Report	Window (front to back)	Sum	Average
1	`10`	`10`	10	10
2	`20`	`10` `20`	30	15
3	`30`	`20` `30` (the `10` left)	50	25
4	`40`	`30` `40` (the `20` left)	70	35

The last report joins the window and the oldest one leaves, so the window slides one step at a time.

Example 2#

text2 lines

Input:  counts = [7], k = 3
Output: [7]

Only one report exists, so the average is that report.

Example 3#

text2 lines

Input:  counts = [5, 6, 6, 5], k = 10
Output: [5, 5, 5, 5]

Fewer than k reports exist at every step, so each average uses all of them: 5, then 11 / 2 rounded down, then 17 / 3, then 22 / 4.

Constraints

1 ≤ length of counts ≤ 10^5
0 ≤ counts[i] ≤ 10^6
1 ≤ k ≤ 10^5

What does n ≤ 10^5 tell you?

A plan that adds up the last k reports again for every report costs about n times k steps. With n and k both near 10^5, that is 10^10, which is too slow.

So keep a running sum. When one report arrives and one leaves, the sum changes by two numbers, and no re-adding is needed.