2090. K Radius Subarray Averages
Problem Description
In this problem, you are given an array nums
containing n
integers, indexed from 0
to n-1
. You are also given an integer k
, which defines a radius. The task is to calculate the k-radius average for each element in the array. The k-radius average for an element at index i
includes all the elements from index i - k
to i + k
, inclusive. To qualify for calculating the average, there must be at least k
elements before and after index i
. If an element doesn't have enough neighbors to satisfy the radius k
, the average for that element will be -1
.
It is important to note that the average is computed using integer division, meaning you add all the elements within the range and then divide by the total number of elements, truncating the result to remove the decimal part.
For example, for the array [1,3,5,7,9]
and k = 1
, the result would be [-1, 3, 5, 7, -1]
because:
- elements at indices
0
and4
don't have enough neighbors for radius1
; - element at index
1
has an average of(1+3+5)/3
, which truncates to3
; - and so on for the elements at indices
2
and3
.
Intuition
The straightforward approach would be to calculate the average for each element individually, which would involve summing elements within the radius for every index, resulting in a time-consuming process with a time complexity of O(n*k).
However, a more efficient method is to use a moving sum (or sliding window). By maintaining a running sum of the last 2k+1
elements, we can compute the k-radius average for the current index by simply dividing this sum by 2k+1
. After computing the average, move the window by increasing the index i
, add the next number in the array to the sum, and subtract the number that just left the window (which would be at index i - 2k
). This way, we only need one pass through the array, resulting in a time complexity of O(n).
The provided Python function getAverages
implements this efficient sliding window approach. An array ans
of the same length as nums
is initially filled with -1
. This will store our results. The variable s
is the sliding sum, which is updated as we iterate over nums
with index i
. If i
is large enough (i >= k * 2
), it means we can compute an average for the element at index i - k
. We add the current value v
to s
, and if the window is valid, we compute the average and update ans[i - k]
. One important detail is the use of integer division s // (k * 2 + 1)
as required by the problem statement. Finally, we return the completed array ans
.
Learn more about Sliding Window patterns.
Solution Approach
The solution provided uses a sliding window technique to efficiently compute each k-radius average in a single pass through the input array nums
.
Here's an in-depth explanation of the algorithm's steps:
-
Initialize a running sum,
s
, which will keep track of the sum of elements in the current window. We will also initialize an arrayans
with the same length asnums
filled with-1
s, to store our results. -
Iterate through the array
nums
with both index and value (i
andv
). Increment the running sums
by the valuev
. -
Check if the current index
i
allows us to have a complete window of2k+1
elements. This is determined by the conditioni >= k * 2
. Ifi
is less thank * 2
, we cannot calculate the average fori - k
since we do not have enough elements before indexi
. -
If we do have enough elements, calculate the average for the element at index
i - k
as the running sums
divided by2k+1
. We use integer division//
here as specified by the problem constraints. The result is stored inans[i - k]
. -
Then, to maintain the size of the window, subtract the element at index
i - 2k
from the running sums
. This is the element that's falling out of our window as we move forward. -
Continue this process until all elements have been visited, and the
ans
array is fully populated with the k-radius averages where possible or-1
where the average cannot be calculated.
The algorithm makes use of simple data structures which are a running sum variable s
and an array ans
to hold the results. The sliding window pattern here avoids redundantly recalculating the sum for overlapping parts of the window, thus optimizing the process to a time complexity of O(n) where n is the length of the input array.
Here's the core code snippet that illustrates the algorithm:
1s = 0
2ans = [-1] * len(nums)
3for i, v in enumerate(nums):
4 s += v
5 if i >= k * 2:
6 ans[i - k] = s // (k * 2 + 1)
7 s -= nums[i - k * 2]
By maintaining the sliding window and updating the running sum in this manner, the algorithm efficiently computes the required averages without redundant calculations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution approach with a small example. Assume we have an array nums = [2, 4, 6, 8, 10]
and k = 2
. We want to find the k-radius average for each element.
-
Initialize Variables: We start by initializing the running sum
s = 0
and an arrayans = [-1, -1, -1, -1, -1]
to store the results. -
Iterate Through
nums
: We begin iterating overnums
. At the start, our running sums
will start accumulating values as we iterate:- At index
0
,s = 0 + 2 = 2
. We cannot compute an average yet, as we don't have enough elements before this index. - At index
1
,s = 2 + 4 = 6
. We still cannot compute an average fori - k = -1
. - At index
2
,s = 6 + 6 = 12
. We reach a point where we could compute an average for the first element (i = 2
,k = 2
), but since it's the first element, we can't.
- At index
-
Check For Complete Window: Now, we reach the first index where a complete window
2k+1
is available:- At index
3
,s = 12 + 8 = 20
. - As
i = 3
is not less thank * 2 (4)
, we can't calculate the average fori - k = 1
yet.
- At index
-
Calculate k-Radius Averages:
- At index
4
,s = 20 + 10 = 30
. Sincei = 4 >= k * 2
, we can now calculate the average fori - k = 2
. We compute it ass // (2 * 2 + 1) = 30 // 5 = 6
. The running sum at this point includesnums[0]
throughnums[4]
(values 2, 4, 6, 8, 10). We store6
inans[2]
.
- At index
-
Slide The Window: Before we move to the next iteration (which we don't have in this example, since we've reached the end of the array), we subtract the number that's falling out of the window. Here that's
nums[4 - 2 * 2]
, which isnums[0] = 2
. Thus, we update the running sums = 30 - 2 = 28
.
If we had more elements in the array, we would continue this process. However, since we've reached the end, we're done, and our result array ans
looks like this: [-1, -1, 6, -1, -1]
. The k-radius average is only calculated for the element at index 2 since those at indices 0, 1, 3 and 4 do not have enough neighbors.
This example illustrates the efficiency of the sliding window technique in avoiding redundant calculations. We avoid iterating over each window separately for each element, which significantly reduces the time complexity from O(nk) to O(n).
Solution Implementation
1from typing import List
2
3class Solution:
4 def getAverages(self, nums: List[int], k: int) -> List[int]:
5 # Initialize the sum variable to keep running total of the elements in the sliding window.
6 window_sum = 0
7 # Initialize the result list to -1 for all elements as the default value.
8 averages = [-1] * len(nums)
9
10 # Loop through the list of numbers while calculating the running sum.
11 for index, value in enumerate(nums):
12 window_sum += value
13
14 # Check if the window has reached the size of (k * 2 + 1).
15 # This means we have enough elements to calculate the average for the middle element.
16 if index >= k * 2:
17 # Calculate the average for the middle element in the window and store it in the result list.
18 averages[index - k] = window_sum // (k * 2 + 1)
19 # Subtract the element that's moving out of the sliding window to maintain the correct window size.
20 window_sum -= nums[index - k * 2]
21
22 # Return the final list of averages.
23 return averages
24
1class Solution {
2 public int[] getAverages(int[] nums, int k) {
3 // Get the length of the input array
4 int n = nums.length;
5
6 // Create a new array for storing prefix sums with length of n + 1
7 long[] prefixSums = new long[n + 1];
8
9 // Compute the prefix sums
10 for (int i = 0; i < n; ++i) {
11 prefixSums[i + 1] = prefixSums[i] + nums[i];
12 }
13
14 // Initialize the answer array with -1, which signifies positions where
15 // the k-range average cannot be computed
16 int[] averages = new int[n];
17 Arrays.fill(averages, -1);
18
19 // Determine the averages for the k-range for each valid position
20 for (int i = 0; i < n; ++i) {
21 // Check if current index i allows a full k-range on both sides
22 if (i - k >= 0 && i + k < n) {
23 // Calculate the sum for this k-range
24 long sumForRange = prefixSums[i + k + 1] - prefixSums[i - k];
25 // Calculate the average and cast it to int before storing it in the result array
26 // (k << 1 | 1) calculates the size of the range, which is (2 * k + 1)
27 averages[i] = (int) (sumForRange / (2 * k + 1));
28 }
29 }
30 // Return the completed array with averages and -1 for non-computable positions
31 return averages;
32 }
33}
34
1#include <vector>
2
3class Solution {
4public:
5 // Function to calculate the averages of all possible subarrays of size k*2+1
6 std::vector<int> getAverages(std::vector<int>& nums, int k) {
7 // Determine the size of the input vector
8 int n = nums.size();
9 // Initialize the answer vector with -1 for all elements
10 std::vector<int> ans(n, -1);
11 // Variable to store the sum of the elements within the window
12 long sum = 0;
13
14 // Iterate over the nums vector
15 for (int i = 0; i < n; ++i) {
16 // Add the current element to the sum
17 sum += nums[i];
18
19 // Check if the window has enough elements to calculate the average
20 if (i >= k * 2) {
21 // Calculate the average for the subarray and store it in the answer vector
22 ans[i - k] = sum / (k * 2 + 1);
23 // Remove the element that's no longer in the window from the sum
24 sum -= nums[i - k * 2];
25 }
26 }
27 // Return the answer vector with calculated averages and -1 for rest
28 return ans;
29 }
30};
31
1function getAverages(nums: number[], k: number): number[] {
2 // Initialize the length of the input array for easier reference
3 const arrayLength = nums.length;
4
5 // Initialize the answer array with -1 for all elements
6 // -1 will be used for positions where the average cannot be calculated
7 const averages: number[] = new Array(arrayLength).fill(-1);
8
9 // A running sum of the elements in the current window
10 let windowSum = 0;
11
12 // Iterate over the array of numbers
13 for (let i = 0; i < arrayLength; ++i) {
14 // Add the current element to the running sum
15 windowSum += nums[i];
16
17 // Check if the window has reached the size of k elements on both sides
18 if (i >= k * 2) {
19 // Calculate the average for the middle element of the current window
20 // The window size is k elements before, the element itself, and k elements after (total 2k + 1 elements)
21 averages[i - k] = Math.floor(windowSum / (k * 2 + 1));
22
23 // Subtract the element that is moving out of the window from the running sum
24 // This is the element i - 2k where i is the current index of the traversal
25 windowSum -= nums[i - k * 2];
26 }
27 }
28
29 // Return the array of calculated averages and -1 for elements where it could not be calculated
30 return averages;
31}
32
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the length of the input list nums
. This is because there is a single loop that iterates over all elements of nums
once. Within the loop, operations are done in constant time including calculating the sum for the average and updating the sum by subtracting the element that is falling out of the sliding window.
The space complexity of the code is O(n)
, where n
is the length of the input list nums
. This is due to the ans
list which is initialized to the same length as nums
. There are no other data structures that depend on the size of the input that would increase the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com 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
LeetCode 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 we
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 algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.