K Radius Subarray Averages - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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.
Approach 1: Brute Force Approach
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.
Complexity
Time Complexity: O(n*k), where n is the size of the array.
Space Complexity: O(n), for the output array.
Approach 2: Sliding Window Approach
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.
Complexity
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.
Approach 3: Sliding Window
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
K Radius Subarray Averages | Sliding Window | Leetcode-2090 | AMAZON | Explanation ➕ Live Coding • codestorywithMIK • 12,780 views views
Watch 9 more video solutions →Frequently Asked Questions
Is K Radius Subarray Averages easy or hard?
K Radius Subarray Averages Python/Java solution
How to solve K Radius Subarray Averages in O(n)?
What is the best approach for K Radius Subarray Averages?
Is K Radius Subarray Averages asked at Google/Amazon/Meta?
What data structure is used in K Radius Subarray Averages?
What is the time complexity of K Radius Subarray Averages?
Ready to solve this problem?
Practice K Radius Subarray Averages with our built-in code editor and test cases.
Practice on FleetCode