# K Radius Subarray Averages
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/k-radius-subarray-averages)
Canonical: https://scaleengineer.com/dsa/problems/k-radius-subarray-averages
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
**Companies:** [Duolingo](https://scaleengineer.com/companies/duolingo)
---
## Problem
You are given a **0-indexed** array `nums` of `n` integers, and an integer `k`.

The **k-radius average** for a subarray of `nums` **centered** at some index `i` with the **radius** `k` is the average of **all** elements in `nums` between the indices `i - k` and `i + k` (**inclusive**). If there are less than `k` elements before **or** after the index `i`, then the **k-radius average** is `-1`.

Build and return _an array_ `avgs` _of length_ `n` _where_ `avgs[i]` _is the **k-radius average** for the subarray centered at index_ `i`.

The **average** of `x` elements is the sum of the `x` elements divided by `x`, using **integer division**. The integer division truncates toward zero, which means losing its fractional part.

* For example, the average of four elements `2`, `3`, `1`, and `5` is `(2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75`, which truncates to `2`.

**Example 1:**

![](https://assets.glich.co/dsa/k-radius-subarray-averages/image0.png) 

**Input:** nums = [7,4,3,9,1,8,5,2,6], k = 3
**Output:** [-1,-1,-1,5,4,4,-1,-1,-1]
**Explanation:**
- avg[0], avg[1], and avg[2] are -1 because there are less than k elements **before** each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
  Using **integer division**, avg[3] = 37 / 7 = 5.
- For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg[6], avg[7], and avg[8] are -1 because there are less than k elements **after** each index.

**Example 2:**

**Input:** nums = [100000], k = 0
**Output:** [100000]
**Explanation:**
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
  avg[0] = 100000 / 1 = 100000.

**Example 3:**

**Input:** nums = [8], k = 100000
**Output:** [-1]
**Explanation:** 
- avg[0] is -1 because there are less than k elements before and after index 0.

**Constraints:**

* `n == nums.length`
* `1 <= n <= 105`
* `0 <= nums[i], k <= 105`

# Approaches
## Brute Force Calculation for Each Subarray
This is a straightforward approach where we iterate through each possible center index `i`. For each `i`, we check if it can form a valid k-radius subarray. If it can, we then iterate through all elements within the radius `k` of `i`, sum them up, and calculate the average. This process is repeated for all indices.
**Time:** O(n * k). For each of the `n` indices, we might perform a sum over `2k + 1` elements. In the worst case, this leads to O(n*k) operations. · **Space:** O(n) to store the result array `avgs`. If the output array is not considered, the auxiliary space is O(1).
**Pros:** Easy to understand and implement.; Directly translates the problem definition into code.
**Cons:** Highly inefficient due to repeated sum calculations for overlapping subarrays.; Will result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
We first create an answer array `avgs` of the same size as `nums` and initialize all its values to `-1`.
We then loop through each index `i` from `0` to `n-1`.
Inside the loop, we check if the current index `i` can be a center of a k-radius subarray. This is possible only if there are at least `k` elements to its left and `k` elements to its right. The condition for this is `i >= k` and `i < n - k`.
If the condition is not met, `avgs[i]` remains `-1`, and we move to the next index.
If the condition is met, we calculate the sum of the elements in the subarray from `i - k` to `i + k`. To avoid integer overflow, we use a `long` variable for the sum.
The number of elements in this subarray is `(i + k) - (i - k) + 1 = 2k + 1`.
We compute the average using integer division: `sum / (2k + 1)`.
The result is stored in `avgs[i]`.
After iterating through all indices, we return the `avgs` array.
```java
import java.util.Arrays;

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] avgs = new int[n];
        Arrays.fill(avgs, -1);

        for (int i = 0; i < n; i++) {
            // Check if a valid k-radius subarray can be formed.
            if (i - k >= 0 && i + k < n) {
                long sum = 0;
                // Calculate the sum of the subarray.
                for (int j = i - k; j <= i + k; j++) {
                    sum += nums[j];
                }
                // Calculate the average and store it.
                avgs[i] = (int) (sum / (2 * k + 1));
            }
        }
        return avgs;
    }
}
```
### Algorithm
* Create an integer array `avgs` of size `n` and fill it with `-1`.
* Iterate through the input array `nums` with index `i` from `0` to `n-1`.
* For each `i`, check if `i - k >= 0` and `i + k < n`.
* If the condition is true:
    a. Initialize a `long` variable `sum = 0`.
    b. Iterate with index `j` from `i - k` to `i + k`.
    c. Add `nums[j]` to `sum`.
    d. After the inner loop, calculate the average `(int) (sum / (2 * k + 1))` and store it in `avgs[i]`.
* Return the `avgs` array.

## Using Prefix Sums
To optimize the sum calculation for each subarray, we can pre-compute prefix sums. A prefix sum array allows us to find the sum of any subarray `[l, r]` in `O(1)` time. We first build the prefix sum array, and then iterate through the possible center indices, calculating each subarray sum efficiently.
**Time:** O(n). It takes O(n) to build the prefix sum array and another O(n) to calculate the averages. · **Space:** O(n). We need an additional O(n) space for the `prefix` array, plus O(n) for the output array.
**Pros:** Significantly more efficient than the brute-force approach.; Calculates each subarray sum in constant time after an initial O(n) setup.
**Cons:** Requires extra space of O(n) for the prefix sum array.
### Explanation
The core idea is to avoid re-calculating the sum of elements for each window. We can pre-calculate the cumulative sum of the `nums` array. Let `prefix[i]` be the sum of elements from `nums[0]` to `nums[i-1]`.
First, we create a `long` array `prefix` of size `n + 1`. `prefix[0]` is initialized to `0`.
We then populate this array: `prefix[i+1] = prefix[i] + nums[i]` for `i` from `0` to `n-1`. Using `long` prevents overflow.
After the `prefix` array is built, we can find the sum of any subarray `nums[l...r]` in constant time using the formula `prefix[r+1] - prefix[l]`.
We create our result array `avgs` of size `n`, initialized with `-1`.
We iterate from `i = k` to `n - 1 - k`, which are the valid center indices.
For each `i`, the subarray is from `l = i - k` to `r = i + k`.
The sum is `prefix[r+1] - prefix[l]`, which is `prefix[i+k+1] - prefix[i-k]`.
The average is this sum divided by the window size `2k + 1`.
We store this average in `avgs[i]`.
```java
import java.util.Arrays;

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] avgs = new int[n];
        Arrays.fill(avgs, -1);

        if (2 * k + 1 > n) {
            return avgs;
        }

        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int windowSize = 2 * k + 1;
        for (int i = k; i < n - k; i++) {
            long sum = prefix[i + k + 1] - prefix[i - k];
            avgs[i] = (int) (sum / windowSize);
        }

        return avgs;
    }
}
```
### Algorithm
* If `2k + 1 > n`, no valid window exists. Return an array of size `n` filled with `-1`.
* Create a `long` prefix sum array `prefix` of size `n + 1`.
* Compute the prefix sums: `prefix[i+1] = prefix[i] + nums[i]` for `i` from `0` to `n-1`.
* Create an integer array `avgs` of size `n` and fill it with `-1`.
* Iterate with index `i` from `k` to `n - 1 - k`.
* For each `i`, calculate the subarray sum using `sum = prefix[i + k + 1] - prefix[i - k]`.
* Calculate the average `(int) (sum / (2 * k + 1))` and store it in `avgs[i]`.
* Return the `avgs` array.

## Optimized Sliding Window
This is the most efficient approach in terms of both time and space. It improves upon the prefix sum method by not requiring an auxiliary array. We maintain a running sum for a 'window' of size `2k+1`. As we slide this window across the array, we update the sum in `O(1)` time by subtracting the element that leaves the window and adding the element that enters.
**Time:** O(n). We iterate through the array a constant number of times. · **Space:** O(n) for the output array. The auxiliary space used is O(1).
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1) auxiliary space.; Most efficient solution for this problem.
**Cons:** The logic for index handling can be slightly tricky to get right.
### Explanation
This method avoids both redundant calculations and the need for an extra `O(n)` space array.
We initialize the result array `avgs` with `-1`.
We define the window size, `diameter = 2k + 1`. If this is larger than `n`, no averages can be computed, so we return the initialized `avgs` array.
We start by calculating the sum of the very first possible window, which is from index `0` to `2k`. We use a `long` variable `windowSum` for this.
The center of this first window is at index `k`. We calculate the average `windowSum / diameter` and store it in `avgs[k]`.
Then, we iterate from index `diameter` up to `n-1`. In each step, we are effectively sliding the window one position to the right.
To update the sum for the new window, we add the new element `nums[i]` that just entered the window and subtract the element `nums[i - diameter]` that just left the window.
The new `windowSum` corresponds to a window centered at `i - k`. We calculate the average and store it in `avgs[i - k]`.
This process continues until the window reaches the end of the array.
```java
import java.util.Arrays;

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        
        if (k == 0) {
            return nums;
        }

        int[] avgs = new int[n];
        Arrays.fill(avgs, -1);

        int windowSize = 2 * k + 1;
        if (windowSize > n) {
            return avgs;
        }

        long windowSum = 0;
        // Calculate sum of the first window
        for (int i = 0; i < windowSize; i++) {
            windowSum += nums[i];
        }
        
        // Calculate average for the first valid center
        avgs[k] = (int) (windowSum / windowSize);

        // Slide the window
        for (int i = windowSize; i < n; i++) {
            // Update sum by adding the new element and removing the old one
            windowSum = windowSum + nums[i] - nums[i - windowSize];
            // The center of the current window is at i - k
            avgs[i - k] = (int) (windowSum / windowSize);
        }

        return avgs;
    }
}
```
### Algorithm
* Handle the edge case `k = 0`. If so, the average at `i` is just `nums[i]`, so return `nums`.
* Initialize an array `avgs` of size `n` with all elements set to `-1`.
* Define the window size `diameter = 2k + 1`.
* If `diameter > n`, no valid window exists, so return `avgs`.
* Calculate the sum of the first window (from index `0` to `diameter - 1`). Store this in a `long` variable `currentSum`.
* The center of this first window is `k`. Calculate the average `(int) (currentSum / diameter)` and store it in `avgs[k]`.
* Iterate with index `i` from `diameter` to `n - 1`. This `i` represents the right edge of the sliding window.
* In each iteration, update the sum: `currentSum = currentSum + nums[i] - nums[i - diameter]`.
* The center of the current window `[i - diameter + 1, i]` is at index `i - k`.
* Calculate the average `(int) (currentSum / diameter)` and store it in `avgs[i - k]`.
* Return the `avgs` array.

# Solutions
### Java

```java
class Solution {
public
  int[] getAverages(int[] nums, int k) {
    int n = nums.length;
    long[] s = new long[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    for (int i = 0; i < n; ++i) {
      if (i - k >= 0 && i + k < n) {
        ans[i] = (int)((s[i + k + 1] - s[i - k]) / (k << 1 | 1));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getAverages(vector<int> &nums, int k) {
    int n = nums.size();
    long s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    vector<int> ans(n, -1);
    for (int i = 0; i < n; ++i) {
      if (i - k >= 0 && i + k < n) {
        ans[i] = (s[i + k + 1] - s[i - k]) / (k << 1 | 1);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]: n = len(nums) ans = [- 1] * n s = list(accumulate(nums, initial=0)) for i in range(n): if i - k >= 0 and i + k < n: ans[i] = (s[i + k + 1] - s[i - k]) // (k << 1 | 1) return ans

```