715. The Average Within Reach of Each Position

For each position i, print the average of the values from i - k to i + k inclusive, rounded DOWN to a whole number. When that range does not fit inside the array, print -1 for that position.

7 4 3 9 1 8 5 2 6, k = 3 -> -1 -1 -1 5 4 4 -1 -1 -1 1 2 3, k = 1 -> -1 2 -1 1 2, k = 0 -> 1 2 9 9 9, k = 5 -> -1 -1 -1

## A fixed window of width 2k + 1, centred rather than trailing

Every other fixed-window problem in this topic reports at the window's right edge. Here the answer belongs to the window's CENTRE, so the window [i-k, i+k] is recorded at index i.

The sweep is unchanged; only the index the result is filed under moves. Filing it at hi instead of hi - k shifts the whole output by k places, which is this problem's characteristic bug.

## The sweep

w = 2k + 1 if w > n: every answer is -1 s = sum of a[0 .. w-1]; res[k] = s / w for i in w .. n-1: s += a[i] - a[i - w] res[i - k] = s / w

Everything outside k .. n-1-k stays -1.

## The width can overflow the array

2k + 1 may exceed n, in which case no position has a full range and every answer is -1. With k up to 10^5 and n as small as 1, that is not a rare case: 9 9 9 with k = 5 is it.

Computing 2k + 1 before checking it against n is safe here, but building the first window before checking is not.

## Rounding down

The average is an integer division, discarding the remainder. In languages where / on integers already truncates toward zero this is automatic, and all values are positive so truncation and flooring agree.

In JavaScript the division is floating point, so it must be floored explicitly. That asymmetry is worth knowing about rather than discovering from a failing test.

## Overflow

2 * 10^5 + 1 values up to 10^5 total 2 * 10^10, past a signed 32 bit integer.

## Cost

Time O(n). Space O(n) for the output.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 100000` - `0 ≤ each value ≤ 100000`