K Radius Subarray Averages — Medium Problem & Solution

The k-radius average of index i is the average of nums[i-k … i+k], rounded down to an integer.

Difficulty: Medium
Topics: Arrays, Sliding Window, Prefix Sum
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 <= 100000
0 <= nums[i], k <= 100000

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 at i - 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 = 0 must 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue