K Radius Subarray Averages

Medium
790.

K Radius Subarray Averages

K Radius Subarray Averages is a medium coding problem on arrays, prefix sum and sliding window, asked in Amazon, Microsoft and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var getAverages = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for K Radius Subarray Averages

  1. Hint 1

    The window is fixed at 2k + 1 elements, centred on the index being filled.

  2. Hint 2

    If 2k + 1 exceeds the array length, every answer is -1.

  3. 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

  1. Fill the output with -1.
  2. If 2k + 1 > n, return it as is.
  3. Sum the first window and write the floor average at index k.
  4. 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

Java

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