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.
2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.
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 <= 105Problem Overview: You are given an integer array nums and an integer k. For every index i, compute the average of the subarray centered at i with radius k, meaning the range [i-k, i+k]. If there are not enough elements on either side, the result for that index is -1. The average uses integer division and the window size is always 2k + 1.
Approach 1: Brute Force Iteration (O(n * k) time, O(1) space)
The direct approach checks every index as a potential center. For each valid index i, iterate from i-k to i+k, compute the sum of the 2k + 1 elements, and divide by the window size to get the average. If the index is too close to the boundaries (less than k from the start or end), assign -1. This method repeatedly recomputes sums for overlapping subarrays, which leads to unnecessary work. Time complexity becomes O(n * k) because each center potentially scans up to 2k + 1 elements. Space complexity remains O(1) aside from the output array. This approach is useful for understanding the problem but does not scale well when k is large.
Approach 2: Sliding Window (O(n) time, O(1) space)
The optimized solution treats the range [i-k, i+k] as a fixed-size window of length 2k + 1. Instead of recalculating the sum for each center, maintain a running sum while sliding the window across the array. Start by computing the sum of the first window. When the window moves one step right, subtract the element leaving the window and add the new element entering it. This keeps the update constant time. The center of each valid window is simply left + k, where left is the window's starting index. Each element is added and removed at most once, giving O(n) time complexity and O(1) extra space. This pattern is a classic application of the sliding window technique on an array.
The key insight is that consecutive windows overlap heavily. Instead of recomputing sums, reuse the previous window's sum and adjust it by removing one element and adding another. This reduces repeated work and makes the algorithm linear.
Recommended for interviews: The sliding window approach is what interviewers expect. It demonstrates that you recognize overlapping subproblems and can optimize repeated computations. Starting with the brute force approach shows you understand the definition of the K-radius average, but moving quickly to the O(n) sliding window solution shows strong algorithmic intuition.
This approach involves iterating over each element in the array and calculating the subarray sum for each index considering the radius. If there is an insufficient number of elements, return -1 for that index. The average is computed using integer division.
This C code implements the brute force approach where for each index, we calculate the sum of its k-radius subarray. If the index doesn't have enough elements on either side, it sets the result for that position to -1.
Time Complexity: O(n*k), where n is the size of the array.
Space Complexity: O(n), for the output array.
The sliding window approach helps optimize the brute force method by avoiding redundant calculations when sums overlap, significantly reducing the time complexity.
This solution implements a sliding window to accumulate the sum over a moving range, improving efficiency compared to calculating the sum from scratch for each subarray.
Time Complexity: O(n), as each element is added and removed from the sum at most once.
Space Complexity: O(n), for storing the results.
The length of a subarray with radius k is k times 2 + 1, so we can maintain a window of size k times 2 + 1 and denote the sum of all elements in the window as s.
We create an answer array ans of length n, initially setting each element to -1.
Next, we traverse the array nums, adding the value of nums[i] to the window sum s. If i geq k times 2, it means the window size is k times 2 + 1, so we set ans[i-k] = \frac{s}{k times 2 + 1}. Then, we remove the value of nums[i - k times 2] from the window sum s. Continue traversing the next element.
Finally, return the answer array.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n*k), where n is the size of the array. |
| Sliding Window Approach | Time Complexity: O(n), as each element is added and removed from the sum at most once. |
| Sliding Window | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration | O(n * k) | O(1) | Good for understanding the definition of K-radius averages or when k is very small |
| Sliding Window | O(n) | O(1) | Best general solution when computing fixed-size subarray sums efficiently |
K Radius Subarray Averages | Sliding Window | Leetcode-2090 | AMAZON | Explanation ➕ Live Coding • codestorywithMIK • 11,190 views views
Watch 9 more video solutions →Practice K Radius Subarray Averages with our built-in code editor and test cases.
Practice on FleetCode