K Radius Subarray Averages
MedPrompt
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, and5is(2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to2.
Example 1:
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.length1 <= n <= 1050 <= nums[i], k <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Create an integer array
avgsof sizenand fill it with-1. - Iterate through the input array
numswith indexifrom0ton-1. - For each
i, check ifi - k >= 0andi + k < n. - If the condition is true:
a. Initialize a
longvariablesum = 0. b. Iterate with indexjfromi - ktoi + k. c. Addnums[j]tosum. d. After the inner loop, calculate the average(int) (sum / (2 * k + 1))and store it inavgs[i]. - Return the
avgsarray.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
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.
Algorithm
- If
2k + 1 > n, no valid window exists. Return an array of sizenfilled with-1. - Create a
longprefix sum arrayprefixof sizen + 1. - Compute the prefix sums:
prefix[i+1] = prefix[i] + nums[i]forifrom0ton-1. - Create an integer array
avgsof sizenand fill it with-1. - Iterate with index
ifromkton - 1 - k. - For each
i, calculate the subarray sum usingsum = prefix[i + k + 1] - prefix[i - k]. - Calculate the average
(int) (sum / (2 * k + 1))and store it inavgs[i]. - Return the
avgsarray.
Walkthrough
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].
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Handle the edge case
k = 0. If so, the average atiis justnums[i], so returnnums. - Initialize an array
avgsof sizenwith all elements set to-1. - Define the window size
diameter = 2k + 1. - If
diameter > n, no valid window exists, so returnavgs. - Calculate the sum of the first window (from index
0todiameter - 1). Store this in alongvariablecurrentSum. - The center of this first window is
k. Calculate the average(int) (currentSum / diameter)and store it inavgs[k]. - Iterate with index
ifromdiameterton - 1. Thisirepresents 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 indexi - k. - Calculate the average
(int) (currentSum / diameter)and store it inavgs[i - k]. - Return the
avgsarray.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.