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 index i + k (inclusive)
If there aren't enough elements before or after index i (meaning i - k < 0 or i + 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 of 2k + 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 position i - k
Updates the window by adding the new element and removing the oldest element

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 index i
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 length n, 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 sum s
Check window size: When i >= k * 2, we have accumulated exactly k * 2 + 1 elements
- This means our window now spans from index i - k * 2 to index i
- The center of this window is at index i - k
Calculate average: Set ans[i - k] = s // (k * 2 + 1) using integer division
Slide window: Remove the leftmost element nums[i - k * 2] from sum s 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 size 2k + 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 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example 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 or long 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 of i >= k * 2
Calculating center as i - k - 1 or i - k + 1 instead of i - k
Incorrectly removing element at index i - k * 2 - 1 or i - k * 2 + 1

Solution:

Remember: When at index i, you have collected i + 1 elements
For a valid window of size 2k + 1, you need index i to be at least 2k
The center of window ending at i is always at i - k
Verify with small examples: if k=1, at i=2, window is [0,1,2] with center at index 1

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 of 2 * 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)

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know

2090. K Radius Subarray Averages

Problem Description

Intuition

Solution Approach

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Integer Overflow with Large Arrays and Values

2. Off-by-One Errors in Index Calculations

3. Handling Edge Cases with Small Arrays

4. Incorrect Window Size Calculation

5. Premature Window Removal

Recommended Readings