K Radius Subarray Averages — LeetCode 2090 Python Solution

The problem

You are given a 0-indexed array nums of n integers, and an integer k. The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive).

Example

Input

nums = [7,4,3,9,1,8,5,2,6], k = 3

Output

[-1,-1,-1,5,4,4,-1,-1,-1]

Explanation

- avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index.

Python solution

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        ans = [-1] * n
        s = 0
        for i, x in enumerate(nums):
            s += x
            if i >= k * 2:
                ans[i - k] = s // (k * 2 + 1)
                s -= nums[i - k * 2]
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2090. K Radius Subarray Averages is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems