< Back

2090. K Radius Subarray Averages

Sliding window problem where we maintain an array of averages for a window of size 2*k+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 2*k+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.