Sliding window problem where we maintain an array of averages for a window of size 2k+1. To facilitate this solution, we go ahead and create an array to store our result. We also check to see if the size of the window 2k+1 is greater than the size of the array, n. If so, just return an array of -1.
First we calculate the average of the first window, and place the result at array[k]. We iterate through the array from k+1 to n-k. Like always with our sliding window solutions, we subtract the left hand amount, array[i - k + 1], from the total and add the right hand amount, array[i + k]. We calcuate the average and set array[i] to the result.
The solution is as follows:
class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
if k == 0: return nums
n = len(nums)
averages = [-1] * n
if 2 * k + 1 > n: return averages
window_sum = sum(nums[:2 * k + 1])
averages[k] = window_sum // (2 * k + 1)
for i in range(k + 1, n - k):
window_sum = window_sum - nums[i - (k + 1)] + nums[i + k]
averages[i] = window_sum // (2 * k + 1)
return averages_ Time Complexity:
O(n) - We traverse the array once.
_ Space Complexity:
O(n) - We maintain an array of size n to store our result.