K Radius Subarray Averages

K Radius Subarray Averages

1. What is this problem about?

The K Radius Subarray Averages interview question asks you to calculate the average of all windows of size $2k + 1$ centered at each index. For each index i, if there are at least k elements to its left and k to its right, calculate the average of the range [i-k, i+k]. Otherwise, the value at that index is -1.

2. Why is this asked in interviews?

Meta and Amazon use the K Radius coding problem to assess a candidate's basic Sliding Window and Prefix Sum proficiency. It tests if you can avoid redundant summations ($O(N \cdot K)$) and achieve $O(N)$ performance. It evaluation your ability to handle integer division and large sums.

3. Algorithmic pattern used

This problem is best solved using Prefix Sums or a Sliding Window.

1. Prefix Sum: Pre-calculate prefixSum[i] as the sum of elements from index 0 to $i-1$.
2. Range Sum: The sum of nums[i-k...i+k] is prefixSum[i+k+1] - prefixSum[i-k].
3. Sliding Window: Alternatively, maintain a running currentWindowSum. As you move to the next center, subtract the element that leaves the window and add the new one.
4. Average: avg = currentSum / (2k + 1).

4. Example explanation

nums = [7, 4, 3, 9, 1], k = 1

• Index 0: No left neighbor. Result -1.
• Index 1: Window [0, 2] is [7, 4, 3]. Sum 14. Avg $14 / 3 = 4$.
• Index 2: Window [1, 3] is [4, 3, 9]. Sum 16. Avg $16 / 3 = 5$.
• Index 3: Window [2, 4] is [3, 9, 1]. Sum 13. Avg $13 / 3 = 4$.
• Index 4: No right neighbor. Result -1. Result: [-1, 4, 5, 4, -1].

5. Common mistakes candidates make

• Integer Overflow: Forgetting that the sum of a window can exceed $2^{31}-1$, requiring 64-bit integers (long).
• Incorrect window size: Using $2k$ or $k+1$ instead of $2k+1$.
• Redundant sum: Using sum(nums[i-k:i+k+1]) inside a loop, making it $O(N \cdot K)$.

6. Interview preparation tip

For any "moving average" or "moving sum" problem, the Prefix Sum interview pattern is usually the safest and easiest to implement. It handles any range query in $O(1)$ without the need for complex pointer logic.