Sponsored
Sponsored
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.
Time Complexity: O(n*k), where n is the size of the array.
Space Complexity: O(n), for the output array.
1def getAverages(nums, k):
2 n = len(nums)
3 avgs = [-1] * n
4 sub_array_size = 2 * k + 1
5
6 for i in range(k, n - k):
7 total = 0
8 for j in range(i - k, i + k + 1):
9 total += nums[j]
10 avgs[i] = total // sub_array_size
11
12 return avgs
13
14nums = [7, 4, 3, 9, 1, 8, 5, 2, 6]
15k = 3
16print(getAverages(nums, k))This Python solution follows a brute force pattern, using nested loops to sum the elements within the k-radius around each valid index, and sets -1 where not applicable.
The sliding window approach helps optimize the brute force method by avoiding redundant calculations when sums overlap, significantly reducing the time 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.
1def
This Python code uses a sliding window approach that updates the sum dynamically by removing the element that's out-of-window and adding the new element as the window slides.