Watch 10 video solutions for K Radius Subarray Averages, a medium level problem involving Array, Sliding Window. This walkthrough by codestorywithMIK has 11,190 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |