K Radius Subarray Averages

Medium Arrays & Hashing Sliding Window · Fixed Original on LeetCode

K Radius Subarray Averages is a medium arrays & hashing problem solved with the sliding window · fixed pattern. The best approach, optimal (sliding window of size 2k + 1), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from brute force up.

Problem

For each index i, the k-radius average is the integer average of the elements from i - k to i + k inclusive. If there are fewer than k elements on either side, the answer for i is -1. Return the array of answers.

Examples

Example 1

Input: nums = [4, 1, 7, 3, 5, 2], k = 1
Output: [-1, 4, 3, 5, 3, -1]
Why: Index 1 averages [4,1,7] = 12 / 3 = 4. The ends lack a full radius, so -1.

Example 2

Input: nums = [9], k = 0
Output: [9]

Constraints

1 <= n <= 10^5
0 <= nums[i], k <= 10^5
Integer division, truncating toward zero.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force	`O(n · k)`	`O(1)`
Optimal (sliding window of size 2k + 1)	`O(n)`	`O(1)`

1Brute force

TimeO(n · k)

SpaceO(1)Besides the output.

For each index with a full radius, sum its 2k + 1 neighbours from scratch.

Fill the answer with -1.
For i from k to n - k - 1, sum nums[i-k..i+k] and divide.

Java

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] out = new int[n];
        Arrays.fill(out, -1);
        for (int i = k; i + k < n; i++) {
            long sum = 0;
            for (int j = i - k; j <= i + k; j++) sum += nums[j];
            out[i] = (int) (sum / (2L * k + 1));
        }
        return out;
    }
}

2Optimal (sliding window of size 2k + 1)

TimeO(n)

SpaceO(1)Besides the output.

Slide a window of width w = 2k + 1. When the window ends at index r, its centre is r - k, so write the average there.

Fill the answer with -1; if w > n, return it.
Keep a running long sum while r moves right.
Once r >= w - 1: out[r - k] = sum / w, then remove nums[r - w + 1].

Java

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length, w = 2 * k + 1;
        int[] out = new int[n];
        Arrays.fill(out, -1);
        if (w > n) return out;
        long sum = 0;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            if (r >= w - 1) {
                out[r - k] = (int) (sum / w);
                sum -= nums[r - w + 1];
            }
        }
        return out;
    }
}

Edge cases to test

k = 0 (every answer is the element itself)
2k + 1 > n (every answer is -1)
Window sums overflow int; use long

Hints

Hint 1

Each answer is the average of a fixed-size window of 2k + 1 elements.

FAQ

What is the best time complexity for K Radius Subarray Averages?

Optimal (sliding window of size 2k + 1) runs in O(n) time and O(1) extra space.

Which pattern does K Radius Subarray Averages use?

It is a arrays & hashing problem that uses the sliding window · fixed pattern. Other problems with the same pattern: Maximum Average Subarray I, Maximum Number of Vowels in a Substring of Given Length.

Is there a brute force solution for K Radius Subarray Averages?

Yes. Brute force takes O(n · k) time and O(1) space. For each index with a full radius, sum its 2k + 1 neighbours from scratch.

Which edge cases should I test for K Radius Subarray Averages?

k = 0 (every answer is the element itself); 2k + 1 n (every answer is -1); Window sums overflow int; use long.