K Radius Subarray Averages
Description
Given a 0-indexed array nums of n integers and an integer k, build and return an array avgs where avgs[i] is the k-radius average for the subarray centered at index i. The k-radius average is the average of all elements between indices i-k and i+k (inclusive). If there are less than k elements before or after index i, the k-radius average is -1. Use integer division (truncate toward zero).
Example 1:
Input: nums = [7, 4, 3, 9, 1, 8, 5, 2, 6], k = 3
Output: [-1, -1, -1, 5, 4, 4, -1, -1, -1]
Explanation:
- Indices 0, 1, 2 have less than k elements before them, so avgs[i] = -1.
- For i=3: window [0..6] = 7+4+3+9+1+8+5 = 37, avg = 37/7 = 5
- For i=4: window [1..7] = 4+3+9+1+8+5+2 = 32, avg = 32/7 = 4
- For i=5: window [2..8] = 3+9+1+8+5+2+6 = 34, avg = 34/7 = 4
- Indices 6, 7, 8 have less than k elements after them, so avgs[i] = -1.
Example 2:
Input: nums = [100000], k = 0
Output: [100000]
Explanation: k=0 means window of size 1, so each element is its own average.
Example 3:
Input: nums = [8], k = 100000
Output: [-1]
Explanation: k is larger than array, so no valid k-radius average exists.
Constraints
n == nums.length1 <= n <= 10^50 <= nums[i], k <= 10^5
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Sliding window with prefix sum
- Approach
- For valid indices i (where i >= k and i < n-k), compute sum of window of size 2k+1 and divide by window size
- Complexity
- Use prefix sum array for O(1) range sum queries, or sliding window
Solutions
Show PY Solution
def solution(nums, k):
sums = [0]
for i in range(len(nums)):
sums.append(nums[i] + sums[-1])
avgs = [-1] * len(nums)
for i in range(k, len(nums) - k):
left = i - k
right = i + k + 1
s_left = sums[left]
s_right = sums[right]
avgs[i] = (s_right - s_left) // (1 + 2 * k)
return avgs