2090. K Radius Subarray Averages
Problem Description
You are given an array nums
of n
integers (0-indexed) and an integer k
.
For each index i
in the array, you need to calculate the k-radius average, which is defined as:
- The average of all elements from index
i - k
to indexi + k
(inclusive) - If there aren't enough elements before or after index
i
(meaningi - k < 0
ori + k >= n
), then the k-radius average is-1
The task is to return an array avgs
of length n
where avgs[i]
contains the k-radius average for the subarray centered at index i
.
Important details:
- The average should use integer division (truncate toward zero, discarding any fractional part)
- For example,
11 / 4 = 2
(not 2.75) - A k-radius subarray has exactly
2k + 1
elements when valid
Example visualization:
If k = 2
and we're looking at index i = 3
, we would average elements at indices [1, 2, 3, 4, 5]
(from i - 2
to i + 2
).
The solution uses a sliding window approach to efficiently calculate these averages:
- Maintains a window sum
s
of2k + 1
consecutive elements - Initializes all answers to
-1
- As the window slides through the array, when it reaches full size at index
i >= 2k
, it calculates the average for the center positioni - k
- Updates the window by adding the new element and removing the oldest element
Intuition
The naive approach would be to calculate the sum for each valid position independently - for each index i
, sum up all elements from i - k
to i + k
and divide by 2k + 1
. However, this would result in recalculating overlapping elements multiple times, leading to inefficient time complexity.
The key observation is that consecutive k-radius subarrays overlap significantly. When we move from index i
to i + 1
, the subarrays centered at these indices differ by only two elements:
- We lose the leftmost element of the previous subarray (at index
i - k
) - We gain a new rightmost element (at index
i + k + 1
)
This insight naturally leads to a sliding window technique. Instead of recalculating the entire sum each time, we can:
- Maintain a running sum of the current window
- Add one element to the right and remove one element from the left as we slide
Another important realization is about the positioning. When we're at index i
in our traversal and have accumulated 2k + 1
elements (meaning i >= 2k
), the center of this window is actually at index i - k
. This is because:
- The window spans from index
i - 2k
to indexi
- The center of this range is at
(i - 2k + i) / 2 = i - k
By maintaining this sliding window and carefully tracking which position corresponds to the center of our current window, we can calculate all k-radius averages in a single pass through the array, achieving optimal O(n)
time complexity.
Learn more about Sliding Window patterns.
Solution Approach
The solution implements a sliding window technique to efficiently calculate the k-radius averages:
1. Initialization:
- Create an answer array
ans
of lengthn
, initialized with all-1
values (handles edge cases where k-radius average cannot be computed) - Initialize a sum variable
s = 0
to maintain the current window sum
2. Sliding Window Process:
For each element at index i
in nums
:
- Add to window: Add
nums[i]
to the running sums
- Check window size: When
i >= k * 2
, we have accumulated exactlyk * 2 + 1
elements- This means our window now spans from index
i - k * 2
to indexi
- The center of this window is at index
i - k
- This means our window now spans from index
- Calculate average: Set
ans[i - k] = s // (k * 2 + 1)
using integer division - Slide window: Remove the leftmost element
nums[i - k * 2]
from sums
to prepare for the next iteration
3. Why this works:
- The condition
i >= k * 2
ensures we only calculate averages when we have a complete window of size2k + 1
- For indices where
i < k * 2
, there aren't enough elements to form a complete window centered at earlier positions, so those remain-1
- Similarly, the last
k
positions in the array will also remain-1
since they can't be centers of complete windows
Time and Space Complexity:
- Time:
O(n)
- single pass through the array - Space:
O(1)
extra space (not counting the output array)
The elegance of this approach lies in maintaining just one running sum and updating it incrementally, avoiding redundant calculations while correctly mapping each window to its center position.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution with nums = [7, 4, 3, 9, 1, 8, 5, 2, 6]
and k = 2
.
Initial Setup:
- We need windows of size
2k + 1 = 5
elements - Initialize
ans = [-1, -1, -1, -1, -1, -1, -1, -1, -1]
- Start with sum
s = 0
Step-by-step execution:
i = 0: Add nums[0] = 7 to sum → s = 7
- Window size = 1 (need 5), no average calculated
i = 1: Add nums[1] = 4 to sum → s = 11
- Window size = 2 (need 5), no average calculated
i = 2: Add nums[2] = 3 to sum → s = 14
- Window size = 3 (need 5), no average calculated
i = 3: Add nums[3] = 9 to sum → s = 23
- Window size = 4 (need 5), no average calculated
i = 4: Add nums[4] = 1 to sum → s = 24
- Window size = 5 ✓ (i >= k*2)
- Window covers indices [0,1,2,3,4], center at i-k = 2
- Calculate: ans[2] = 24 // 5 = 4
- Remove nums[0] = 7 from sum → s = 17
i = 5: Add nums[5] = 8 to sum → s = 25
- Window covers indices [1,2,3,4,5], center at i-k = 3
- Calculate: ans[3] = 25 // 5 = 5
- Remove nums[1] = 4 from sum → s = 21
i = 6: Add nums[6] = 5 to sum → s = 26
- Window covers indices [2,3,4,5,6], center at i-k = 4
- Calculate: ans[4] = 26 // 5 = 5
- Remove nums[2] = 3 from sum → s = 23
i = 7: Add nums[7] = 2 to sum → s = 25
- Window covers indices [3,4,5,6,7], center at i-k = 5
- Calculate: ans[5] = 25 // 5 = 5
- Remove nums[3] = 9 from sum → s = 16
i = 8: Add nums[8] = 6 to sum → s = 22
- Window covers indices [4,5,6,7,8], center at i-k = 6
- Calculate: ans[6] = 22 // 5 = 4
- Remove nums[4] = 1 from sum → s = 21
Final Result: ans = [-1, -1, 4, 5, 5, 5, 4, -1, -1]
The first two and last two positions remain -1 because they cannot be centers of complete 5-element windows.
Solution Implementation
1class Solution:
2 def getAverages(self, nums: List[int], k: int) -> List[int]:
3 """
4 Calculate k-radius averages for each element in the array.
5 For each valid index i, compute the average of elements from i-k to i+k.
6
7 Args:
8 nums: List of integers
9 k: Radius for calculating averages
10
11 Returns:
12 List where each element is either the k-radius average or -1 if not enough elements
13 """
14 n = len(nums)
15 # Initialize result array with -1 (default for indices without enough neighbors)
16 result = [-1] * n
17
18 # Running sum for the sliding window
19 window_sum = 0
20
21 # Iterate through the array
22 for i, num in enumerate(nums):
23 # Add current element to the window sum
24 window_sum += num
25
26 # Check if we have enough elements for a valid k-radius average
27 # We need at least 2k + 1 elements (k on left, current, k on right)
28 if i >= k * 2:
29 # Calculate average for the center of the current window
30 # The center is at index (i - k)
31 result[i - k] = window_sum // (k * 2 + 1)
32
33 # Remove the leftmost element from the window for next iteration
34 window_sum -= nums[i - k * 2]
35
36 return result
37
1class Solution {
2 public int[] getAverages(int[] nums, int k) {
3 int arrayLength = nums.length;
4 int[] result = new int[arrayLength];
5
6 // Initialize all elements to -1 (default for positions without enough neighbors)
7 Arrays.fill(result, -1);
8
9 // Use long to avoid integer overflow when calculating sum
10 long windowSum = 0;
11
12 // Iterate through the array
13 for (int currentIndex = 0; currentIndex < arrayLength; ++currentIndex) {
14 // Add current element to the sliding window sum
15 windowSum += nums[currentIndex];
16
17 // Check if we have enough elements for a complete window (k elements before and after)
18 // Window size is 2*k + 1 (k before, current element, k after)
19 if (currentIndex >= k * 2) {
20 // Calculate the center position of the current window
21 int centerIndex = currentIndex - k;
22
23 // Calculate and store the average at the center position
24 // Divide by window size (2*k + 1) to get the average
25 result[centerIndex] = (int) (windowSum / (k * 2 + 1));
26
27 // Remove the leftmost element from the window sum for the next iteration
28 windowSum -= nums[currentIndex - k * 2];
29 }
30 }
31
32 return result;
33 }
34}
35
1class Solution {
2public:
3 vector<int> getAverages(vector<int>& nums, int k) {
4 int n = nums.size();
5 vector<int> result(n, -1); // Initialize result array with -1 (default for positions without valid k-radius average)
6
7 long long windowSum = 0; // Use long long to prevent integer overflow when summing
8 int windowSize = 2 * k + 1; // Total window size: k elements on left + current element + k elements on right
9
10 // Iterate through the array
11 for (int i = 0; i < n; ++i) {
12 // Add current element to the sliding window sum
13 windowSum += nums[i];
14
15 // Check if we have enough elements to form a complete window
16 if (i >= 2 * k) {
17 // Calculate average for the center position of the current window
18 // The center is at index (i - k)
19 result[i - k] = windowSum / windowSize;
20
21 // Remove the leftmost element from the sliding window
22 // to prepare for the next iteration
23 windowSum -= nums[i - 2 * k];
24 }
25 }
26
27 return result;
28 }
29};
30
1/**
2 * Calculates k-radius averages for each element in the array
3 * A k-radius average for index i is the average of elements from index (i-k) to (i+k)
4 * Returns -1 for indices where k-radius average cannot be calculated
5 *
6 * @param nums - The input array of numbers
7 * @param k - The radius for calculating averages
8 * @returns Array of k-radius averages, -1 where not calculable
9 */
10function getAverages(nums: number[], k: number): number[] {
11 const arrayLength: number = nums.length;
12 const result: number[] = Array(arrayLength).fill(-1);
13
14 // Running sum for the sliding window
15 let windowSum: number = 0;
16
17 // Window size for k-radius average (k elements on each side + center element)
18 const windowSize: number = k * 2 + 1;
19
20 for (let currentIndex: number = 0; currentIndex < arrayLength; ++currentIndex) {
21 // Add current element to the window sum
22 windowSum += nums[currentIndex];
23
24 // Check if we have enough elements to calculate k-radius average
25 // We need at least (2k + 1) elements in total
26 if (currentIndex >= k * 2) {
27 // Calculate average for the center position of current window
28 // The center is at index (currentIndex - k)
29 result[currentIndex - k] = Math.floor(windowSum / windowSize);
30
31 // Remove the leftmost element from the window as we slide right
32 windowSum -= nums[currentIndex - k * 2];
33 }
34 }
35
36 return result;
37}
38
Time and Space Complexity
Time Complexity: O(n)
, where n
is the length of the array nums
. The algorithm iterates through the array exactly once with a single for loop. Each operation inside the loop (addition, subtraction, integer division, and array access) takes constant time O(1)
. Therefore, the overall time complexity is linear.
Space Complexity: O(1)
(excluding the output array). The algorithm uses only a constant amount of extra space: the variable s
for maintaining the running sum, and loop variables i
and x
. If we include the output array ans
, the space complexity would be O(n)
, but following the convention stated in the reference answer, we ignore the space consumption of the answer array.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Integer Overflow with Large Arrays and Values
When dealing with large arrays where elements can be up to 10^5
and k
can be large, the window sum might exceed the integer limit in some programming languages.
Problem Example:
- Array with 100,000 elements, each valued at 100,000
- With
k = 50,000
, window size = 100,001 - Sum could reach ~10^10, exceeding 32-bit integer limits
Solution:
- In Python, this isn't an issue due to arbitrary precision integers
- In languages like Java/C++, use
long
orlong long
for the sum variable - Consider the maximum possible sum based on constraints
2. Off-by-One Errors in Index Calculations
The relationship between the window position and the center index can be confusing, leading to incorrect index mapping.
Common Mistakes:
- Using
i >= k * 2 - 1
instead ofi >= k * 2
- Calculating center as
i - k - 1
ori - k + 1
instead ofi - k
- Incorrectly removing element at index
i - k * 2 - 1
ori - k * 2 + 1
Solution:
- Remember: When at index
i
, you have collectedi + 1
elements - For a valid window of size
2k + 1
, you need indexi
to be at least2k
- The center of window ending at
i
is always ati - k
- Verify with small examples: if
k=1
, ati=2
, window is[0,1,2]
with center at index1
3. Handling Edge Cases with Small Arrays
When the array length is smaller than 2k + 1
, the entire result should be -1
.
Problem Example:
nums = [1, 2, 3]
,k = 2
(needs window size 5, but array has only 3 elements)
Solution:
- The algorithm naturally handles this by never entering the condition
i >= k * 2
- But it's good to add an early check for clarity:
if n < k * 2 + 1: return [-1] * n
4. Incorrect Window Size Calculation
Confusing the window size formula or using 2k
instead of 2k + 1
.
Common Mistake:
- Dividing by
2 * k
instead of2 * k + 1
- This would give incorrect averages
Solution:
- Always remember: k-radius means k elements on each side PLUS the center element
- Total elements = k (left) + 1 (center) + k (right) = 2k + 1
- Double-check the divisor in the average calculation
5. Premature Window Removal
Removing the leftmost element before calculating the average, which would give incorrect results.
Correct Order:
- Add current element to sum
- Check if window is complete
- Calculate and store average
- Remove leftmost element for next iteration
Incorrect Order (Common Mistake):
- Add current element
- Remove leftmost element immediately
- Calculate average (now with wrong sum)
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
https assets algo monster cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in the window The window
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!