K Radius Subarray Averages

Problem

For each index, compute the average of the 2k+1 elements centered on it (k elements on each side). If there are not enough elements on either side, the answer for that index is -1.

Input:  nums = [7,4,3,9,1,8,5,2,6], k = 3
Output: [-1,-1,-1,5,4,4,-1,-1,-1]

Python Solution

def get_averages(nums, k):
    n = len(nums)
    result = [-1] * n
    window = 2 * k + 1
    if window > n:
        return result
    window_sum = sum(nums[:window])
    result[k] = window_sum // window
    for i in range(window, n):
        window_sum += nums[i] - nums[i - window]
        result[i - k] = window_sum // window
    return result

C++ Solution

vector<int> getAverages(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result(n, -1);
    long window = 2L * k + 1;
    if (window > n) return result;
    long windowSum = 0;
    for (int i = 0; i < window; i++) windowSum += nums[i];
    result[k] = windowSum / window;
    for (int i = window; i < n; i++) {
        windowSum += nums[i] - nums[i - window];
        result[i - k] = windowSum / window;
    }
    return result;
}

Java Solution

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        long window = 2L * k + 1;
        if (window > n) return result;
        long windowSum = 0;
        for (int i = 0; i < window; i++) windowSum += nums[i];
        result[k] = (int) (windowSum / window);
        for (int i = (int) window; i < n; i++) {
            windowSum += nums[i] - nums[i - (int) window];
            result[i - k] = (int) (windowSum / window);
        }
        return result;
    }
}

Complexity

Time: O(n) — each element is added once and removed once from the running sum. Space: O(n) for the output array; O(1) extra beyond it.