K Radius Subarray Averages

medium array sliding window

Problem

Given nums and k, build avgs where avgs[i] is the integer average of nums[i−k..i+k] when fully in bounds, otherwise −1.

Inputnums = [7,4,3,9,1,8,5,2,6], k = 3

Output[-1,-1,-1,5,4,4,-1,-1,-1]

avgs[3] = (7+4+3+9+1+8+5)/7 = 5.

nums (comma-separated)

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

function getAverages(nums, k) {
  const n = nums.length;
  const avgs = new Array(n).fill(-1);
  const w = 2 * k + 1;
  if (w > n) return avgs;
  let s = 0;
  for (let i = 0; i < w; i++) s += nums[i];
  avgs[k] = Math.floor(s / w);
  for (let i = k + 1; i < n - k; i++) {
    s += nums[i + k] - nums[i - k - 1];
    avgs[i] = Math.floor(s / w);
  }
  return avgs;
}

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

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

Explanation

For each index we need the average of the 2k+1 numbers centered on it. The slow way would recompute that whole sum at every position. The trick is to keep a running sum of one window and just nudge it as we move right.

First, any index that does not have a full k neighbors on both sides cannot have an average, so we fill the whole answer with -1 up front and bail out early if the window width w = 2*k + 1 is bigger than the array.

We compute the sum of the first full window once and store its floor average at index k. Then for each next center i, we add the new right element nums[i + k] and drop the old left element nums[i - k - 1]. That single add-and-subtract slides the window without rescanning.

Example: nums = [7,4,3,9,1,8,5,2,6], k = 3, so w = 7. The first window covers indices 0..6 with sum 37, giving avgs[3] = 37 // 7 = 5. Sliding to center 4 adds nums[7]=2 and removes nums[0]=7.

Because each step is just one addition and one subtraction, the whole pass is linear time no matter how big k is.

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