K Radius Subarray Averages
Medium · Sliding Window · Array · Sliding Window · Prefix Sum
Problem
You are given an integer array nums of length n and an integer k. The k-radius average at index i is the average of the 2k + 1 values from nums[i - k] to nums[i + k], rounded down (integer division that drops the fractional part).
Return an array avgs of length n where avgs[i] is the k-radius average at i, or -1 when fewer than k values exist on either side of i.
Examples
Input: nums = [4,2,9,1,5,3], k = 1 Output: [-1,5,4,5,3,-1]
Index 1 averages 4, 2 and 9: 15 / 3 = 5. Index 2 averages 2, 9 and 1: 12 / 3 = 4. The two ends lack a neighbor on one side.
Input: nums = [8], k = 0 Output: [8]
With radius 0, each value is its own average.
Input: nums = [1,2], k = 3 Output: [-1,-1]
A window needs 7 values, and the array has only 2.
Constraints
- n == len(nums)
- 1 <= n <= 10^5
- 0 <= nums[i], k <= 10^5
Approaches
- Sum every window from scratch — time O(n · k), space O(n) for the answer
Follow-up
Prefix sums give the same answer: with pre[i] the sum of the first i values, the window at i sums to pre[i + k + 1] - pre[i - k]. That costs O(n) extra space but answers any radius after one pass, which helps when the same array is asked about many radii.
Related problems
Start free on Cariara · Coding problems · System design studio
