K Radius Subarray Averages — Solution in Python, Java & C++
K Radius Subarray Averages solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
K Radius Subarray Averages is a medium coding problem on arrays, prefix sum and sliding window, asked in Amazon, Microsoft and Zoho interviews.
- Difficulty: Medium
- Topics: Arrays, Prefix Sum, Sliding Window
- Asked at: Amazon, Microsoft, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The k-radius average of index i is the average of nums[i-k … i+k], rounded down to an integer. If fewer than k elements exist on either side, the average is -1.
Return an array holding the k-radius average of every index.
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: Index 3 averages 7+4+3+9+1+8+5 = 37 over 7, which floors to 5.
Example 2
Input: nums = [100000], k = 0
Output: [100000]
Explanation: A radius of 0 is the element itself.
Example 3
Input: nums = [8], k = 100
Output: [-1]
Constraints
1 <= nums.length <= 1000000 <= nums[i], k <= 100000
Hints for K Radius Subarray Averages
Hint 1
The window is fixed at
2k + 1elements, centred on the index being filled.Hint 2
If
2k + 1exceeds the array length, every answer is-1.Hint 3
The running sum reaches
10^5 · 10^5 = 10^10— wider than a 32-bit integer.
How to solve K Radius Subarray Averages
A fixed-size rolling sum. Seed it with the first 2k + 1 elements, write the average at the window's centre, then slide one step at a time.
Approach
- Fill the output with
-1. - If
2k + 1 > n, return it as is. - Sum the first window and write the floor average at index
k. - For each further right end
i, roll the sum and write ati - k.
Why it works
Each index's window is determined by its centre, and neighbouring centres share all but two elements, so the sum rolls in constant time. Indices near either edge genuinely have no full window, which is what the -1 marks.
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Accumulating the sum in a 32-bit integer overflows at the stated limits — use 64-bit.
k = 0must still produce every element, not all-1.- The average floors, so integer division is what is wanted — but only because every value is non-negative.
Reference solution
Python
from typing import List
def getAverages(nums: List[int], k: int) -> List[int]:
n = len(nums)
out = [-1] * n
w = 2 * k + 1
if w > n:
return out
total = sum(nums[:w])
out[k] = total // w
for i in range(w, n):
total += nums[i] - nums[i - w]
out[i - k] = total // w
return outJava
public static int[] getAverages(int[] nums, int k) {
int n = nums.length;
int[] out = new int[n];
Arrays.fill(out, -1);
long w = 2L * k + 1;
if (w > n) return out;
int width = (int) w;
long sum = 0;
for (int i = 0; i < width; i++) sum += nums[i];
out[k] = (int) (sum / w);
for (int i = width; i < n; i++) {
sum += nums[i] - nums[i - width];
out[i - k] = (int) (sum / w);
}
return out;
}C++
vector<int> getAverages(vector<int>& nums, int k) {
int n = (int) nums.size();
vector<int> out(n, -1);
long long w = 2LL * k + 1;
if (w > n) return out;
int width = (int) w;
long long sum = 0;
for (int i = 0; i < width; i++) sum += nums[i];
out[k] = (int) (sum / w);
for (int i = width; i < n; i++) {
sum += nums[i] - nums[i - width];
out[i - k] = (int) (sum / w);
}
return out;
}JavaScript
var getAverages = function(nums, k) {
var n = nums.length;
var out = [];
for (var t = 0; t < n; t++) out.push(-1);
var w = 2 * k + 1;
if (w > n) return out;
var sum = 0;
for (var i = 0; i < w; i++) sum += nums[i];
out[k] = Math.floor(sum / w);
for (var j = w; j < n; j++) {
sum += nums[j] - nums[j - w];
out[j - k] = Math.floor(sum / w);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum