K Radius Subarray Averages solution and explanation
Google
9 more videos on this problem
K Radius Subarray Averages | Sliding Window | Leetcode-2090 | AMAZON | Explanation ➕ Live CodingcodestorywithMIK · 18:21 · 12K views
K Radius Subarray Averages | Leetcode-2090 | AMAZON | Explanation ➕ Live CodingcodestorywithMIK · 24:45 · 6K views
LeetCode 2090 | K Radius Subarray Averages SolutionEngineering Digest · 8:24 · 2K views
K Radius Subarray Averages - Leetcode 2090 - PythonTechError · 8:26 · 1K views
2090. K Radius Subarray Averages | Sliding Window | LeetCode Daily ChallengeDeep Tech · 18:49 · 1K views
2090 K Radius Subarray Averages (Leetcode Medium)Programming Live with Larry · 8:00 · 985 views
K Radius Subarray Averages - LeetCode 2090- PythonAlpha-Code · 22:20 · 466 views
LeetCode Daily Challenge 2090: K-Radius Subarray Averages | C# Solution ExplainedvanAmsen · 6:04 · 457 views
Daily Leetcode #1176: Jun 20, 2023 - 2090. K Radius Subarray AveragesProgramming Live with Larry · 8:04 · 337 views
2090. K Radius Subarray Averages (LeetCode, Java)hakunamatasq · 7:23 · 275 views
The problem
You are given a 0-indexed array nums of n integers, and an integer k.
The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i - k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.
Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.
The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.
- For example, the average of four elements
2,3,1, and5is(2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to2.
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: - avg[0], avg[1], and avg[2] are -1 because there are less than k elements before each index. - The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37. Using integer division, avg[3] = 37 / 7 = 5. - For the subarray centered at index 4, avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4. - For the subarray centered at index 5, avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4. - avg[6], avg[7], and avg[8] are -1 because there are less than k elements after each index.
Example 2:
Input: nums = [100000], k = 0 Output: [100000] Explanation: - The sum of the subarray centered at index 0 with radius 0 is: 100000. avg[0] = 100000 / 1 = 100000.
Example 3:
Input: nums = [8], k = 100000 Output: [-1] Explanation: - avg[0] is -1 because there are less than k elements before and after index 0.
Constraints:
n == nums.length1 <= n <= 1050 <= nums[i], k <= 105
Approach overview
Problem Overview: You are given an integer array nums and an integer k. For every index i, compute the average of the subarray centered at i with radius k, meaning the range [i-k, i+k]. If there are not enough elements on either side, the result for that index is -1. The average uses integer division and the window size is always 2k + 1.
Approach 1: Brute Force Iteration (O(n * k) time, O(1) space)
The direct approach checks every index as a potential center. For each valid index i, iterate from i-k to i+k, compute the sum of the 2k + 1 elements, and divide by the window size to get the average. If the index is too close to the boundaries (less than k from the start or end), assign -1. This method repeatedly recomputes sums for overlapping subarrays, which leads to unnecessary work. Time complexity becomes O(n * k) because each center potentially scans up to 2k + 1 elements. Space complexity remains O(1) aside from the output array. This approach is useful for understanding the problem but does not scale well when k is large.
Approach 2: Sliding Window (O(n) time, O(1) space)
The optimized solution treats the range [i-k, i+k] as a fixed-size window of length 2k + 1. Instead of recalculating the sum for each center, maintain a running sum while sliding the window across the array. Start by computing the sum of the first window. When the window moves one step right, subtract the element leaving the window and add the new element entering it. This keeps the update constant time. The center of each valid window is simply left + k, where left is the window's starting index. Each element is added and removed at most once, giving O(n) time complexity and O(1) extra space. This pattern is a classic application of the sliding window technique on an array.
The key insight is that consecutive windows overlap heavily. Instead of recomputing sums, reuse the previous window's sum and adjust it by removing one element and adding another. This reduces repeated work and makes the algorithm linear.
Recommended for interviews: The sliding window approach is what interviewers expect. It demonstrates that you recognize overlapping subproblems and can optimize repeated computations. Starting with the brute force approach shows you understand the definition of the K-radius average, but moving quickly to the O(n) sliding window solution shows strong algorithmic intuition.
Approach 1: Brute Force Approach
This approach involves iterating over each element in the array and calculating the subarray sum for each index considering the radius. If there is an insufficient number of elements, return -1 for that index. The average is computed using integer division.
def getAverages(nums, k):
n = len(nums)
avgs = [-1] * n
sub_array_size = 2 * k + 1
for i in range(k, n - k):
total = 0
for j in range(i - k, i + k + 1):
total += nums[j]
avgs[i] = total // sub_array_size
return avgs
nums = [7, 4, 3, 9, 1, 8, 5, 2, 6]
k = 3
print(getAverages(nums, k))import java.util.Arrays;
public class SubarrayAverages {
public static int[] getAverages(int[] nums, int k) {
int n = nums.length;
int[] avgs = new int[n];
Arrays.fill(avgs, -1);
int subArraySize = 2 * k + 1;
for (int i = k; i < n - k; i++) {
long sum = 0;
for (int j = i - k; j <= i + k; j++) {
sum += nums[j];
}
avgs[i] = (int) (sum / subArraySize);
}
return avgs;
}
public static void main(String[] args) {
int[] nums = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int k = 3;
int[] averages = getAverages(nums, k);
for (int avg : averages) {
System.out.print(avg + " ");
}
}
}#include <vector>
#include <iostream>
std::vector<int> getAverages(std::vector<int>& nums, int k) {
int n = nums.size();
std::vector<int> avgs(n, -1);
int subArraySize = 2 * k + 1;
for (int i = k; i < n - k; ++i) {
long sum = 0;
for (int j = i - k; j <= i + k; ++j) {
sum += nums[j];
}
avgs[i] = sum / subArraySize;
}
return avgs;
}
int main() {
std::vector<int> nums = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int k = 3;
std::vector<int> averages = getAverages(nums, k);
for (auto avg : averages) {
std::cout << avg << " ";
}
return 0;
}function getAverages(nums, k) {
const n = nums.length;
const avgs = Array(n).fill(-1);
const subArraySize = 2 * k + 1;
for (let i = k; i < n - k; i++) {
let sum = 0;
for (let j = i - k; j <= i + k; j++) {
sum += nums[j];
}
avgs[i] = Math.floor(sum / subArraySize);
}
return avgs;
}
const nums = [7, 4, 3, 9, 1, 8, 5, 2, 6];
const k = 3;
console.log(getAverages(nums, k));#include <stdio.h>
#include <stdlib.h>
int* getAverages(int* nums, int numsSize, int k, int* returnSize) {
*returnSize = numsSize;
int* avgs = (int*)malloc(numsSize * sizeof(int));
int subArraySize = 2 * k + 1;
for (int i = 0; i < numsSize; ++i) {
if (i < k || i >= numsSize - k) {
avgs[i] = -1;
} else {
long sum = 0;
for (int j = i - k; j <= i + k; ++j) {
sum += nums[j];
}
avgs[i] = sum / subArraySize;
}
}
return avgs;
}
int main() {
int nums[] = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int k = 3;
int returnSize;
int* averages = getAverages(nums, numsSize, k, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", averages[i]);
}
free(averages);
return 0;
}using System;
public class SubarrayAverages {
public static int[] GetAverages(int[] nums, int k) {
int n = nums.Length;
int[] avgs = new int[n];
for (int i = 0; i < n; i++) avgs[i] = -1;
int subArraySize = 2 * k + 1;
for (int i = k; i < n - k; i++) {
long sum = 0;
for (int j = i - k; j <= i + k; j++) {
sum += nums[j];
}
avgs[i] = (int)(sum / subArraySize);
}
return avgs;
}
public static void Main() {
int[] nums = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int k = 3;
int[] averages = GetAverages(nums, k);
Console.WriteLine(string.Join(" ", averages));
}
}This Python solution follows a brute force pattern, using nested loops to sum the elements within the k-radius around each valid index, and sets -1 where not applicable.
Time Complexity: O(n*k), where n is the length of nums, because it computes the sum for each valid subarray.
Space Complexity: O(n), as it stores the result in an array of the same size.
Approach 2: Sliding Window Approach
The sliding window approach helps optimize the brute force method by avoiding redundant calculations when sums overlap, significantly reducing the time complexity.
def getAverages(nums, k):
n = len(nums)
avgs = [-1] * n
sub_array_size = 2 * k + 1
window_sum = 0
for i in range(n):
window_sum += nums[i]
if i >= sub_array_size:
window_sum -= nums[i - sub_array_size]
if i >= sub_array_size - 1:
avgs[i - k] = window_sum // sub_array_size
return avgs
nums = [7, 4, 3, 9, 1, 8, 5, 2, 6]
k = 3
print(getAverages(nums, k))import java.util.Arrays;
public class SubarrayAverages {
public static int[] getAverages(int[] nums, int k) {
int n = nums.length;
int[] avgs = new int[n];
Arrays.fill(avgs, -1);
int subArraySize = 2 * k + 1;
long windowSum = 0;
for (int i = 0; i < n; i++) {
windowSum += nums[i];
if (i >= subArraySize) {
windowSum -= nums[i - subArraySize];
}
if (i >= subArraySize - 1) {
avgs[i - k] = (int) (windowSum / subArraySize);
}
}
return avgs;
}
public static void main(String[] args) {
int[] nums = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int k = 3;
int[] averages = getAverages(nums, k);
for (int avg : averages) {
System.out.print(avg + " ");
}
}
}#include <vector>
#include <iostream>
std::vector<int> getAverages(std::vector<int>& nums, int k) {
int n = nums.size();
std::vector<int> avgs(n, -1);
int subArraySize = 2 * k + 1;
long long windowSum = 0;
for (int i = 0; i < n; ++i) {
windowSum += nums[i];
if (i >= subArraySize) {
windowSum -= nums[i - subArraySize];
}
if (i >= subArraySize - 1) {
avgs[i - k] = windowSum / subArraySize;
}
}
return avgs;
}
int main() {
std::vector<int> nums = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int k = 3;
std::vector<int> averages = getAverages(nums, k);
for (auto avg : averages) {
std::cout << avg << " ";
}
return 0;
}function getAverages(nums, k) {
const n = nums.length;
const avgs = Array(n).fill(-1);
const subArraySize = 2 * k + 1;
let windowSum = 0;
for (let i = 0; i < n; i++) {
windowSum += nums[i];
if (i >= subArraySize) {
windowSum -= nums[i - subArraySize];
}
if (i >= subArraySize - 1) {
avgs[i - k] = Math.floor(windowSum / subArraySize);
}
}
return avgs;
}
const nums = [7, 4, 3, 9, 1, 8, 5, 2, 6];
const k = 3;
console.log(getAverages(nums, k));#include <stdio.h>
#include <stdlib.h>
int* getAverages(int* nums, int numsSize, int k, int* returnSize) {
*returnSize = numsSize;
int* avgs = (int*)malloc(numsSize * sizeof(int));
int subArraySize = 2 * k + 1;
long windowSum = 0;
for (int i = 0; i < numsSize; ++i) {
avgs[i] = -1;
}
for (int i = 0; i < numsSize; ++i) {
windowSum += nums[i];
if (i >= subArraySize) {
windowSum -= nums[i - subArraySize];
}
if (i >= subArraySize - 1) {
avgs[i - k] = windowSum / subArraySize;
}
}
return avgs;
}
int main() {
int nums[] = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int k = 3;
int returnSize;
int* averages = getAverages(nums, numsSize, k, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", averages[i]);
}
free(averages);
return 0;
}using System;
public class SubarrayAverages {
public static int[] GetAverages(int[] nums, int k) {
int n = nums.Length;
int[] avgs = new int[n];
for (int i = 0; i < n; i++) avgs[i] = -1;
int subArraySize = 2 * k + 1;
long windowSum = 0;
for (int i = 0; i < n; ++i) {
windowSum += nums[i];
if (i >= subArraySize) {
windowSum -= nums[i - subArraySize];
}
if (i >= subArraySize - 1) {
avgs[i - k] = (int)(windowSum / subArraySize);
}
}
return avgs;
}
public static void Main() {
int[] nums = {7, 4, 3, 9, 1, 8, 5, 2, 6};
int k = 3;
int[] averages = GetAverages(nums, k);
Console.WriteLine(string.Join(" ", averages));
}
}This Python code uses a sliding window approach that updates the sum dynamically by removing the element that's out-of-window and adding the new element as the window slides.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Sliding Window
The length of a subarray with radius k is k times 2 + 1, so we can maintain a window of size k times 2 + 1 and denote the sum of all elements in the window as s.
We create an answer array ans of length n, initially setting each element to -1.
Next, we traverse the array nums, adding the value of nums[i] to the window sum s. If i geq k times 2, it means the window size is k times 2 + 1, so we set ans[i-k] = \frac{s}{k times 2 + 1}. Then, we remove the value of nums[i - k times 2] from the window sum s. Continue traversing the next element.
Finally, return the answer array.
The time complexity is O(n), where n is the length of the array nums. Ignoring the space consumption of the answer array, the space complexity is O(1).
function getAverages(nums: number[], k: number): number[] {
const n = nums.length;
const ans: number[] = Array(n).fill(-1);
let s = 0;
for (let i = 0; i < n; ++i) {
s += nums[i];
if (i >= k * 2) {
ans[i - k] = Math.floor(s / (k * 2 + 1));
s -= nums[i - k * 2];
}
}
return ans;
}func getAverages(nums []int, k int) []int {
ans := make([]int, len(nums))
for i := range ans {
ans[i] = -1
}
s := 0
for i, x := range nums {
s += x
if i >= k*2 {
ans[i-k] = s / (k*2 + 1)
s -= nums[i-k*2]
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n*k), where n is the length of nums, because it computes the sum for each valid subarray. |
| Sliding Window Approach | Time Complexity: O(n) |
| Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Iteration | O(n * k) | O(1) | Good for understanding the definition of K-radius averages or when k is very small |
| Sliding Window | O(n) | O(1) | Best general solution when computing fixed-size subarray sums efficiently |
Frequently asked questions
Is K Radius Subarray Averages easy or hard?
K Radius Subarray Averages is rated Medium on LeetCode. The difficulty comes from recognizing that repeated subarray sums can be optimized with a sliding window instead of recomputing each range.
K Radius Subarray Averages Python/Java solution
Most implementations follow the same logic across languages: maintain a running window sum and update it while sliding across the array. Python, Java, C++, and JavaScript solutions all achieve O(n) time by updating the window sum instead of recomputing it.
How to solve K Radius Subarray Averages in O(n)?
Maintain a running sum for a window of size 2k + 1. Initialize the first window sum, then slide the window one step at a time by subtracting the element leaving the window and adding the new element entering it. The center index of each valid window receives the computed average using integer division.
What is the best approach for K Radius Subarray Averages?
The sliding window approach is the most efficient solution. It maintains the sum of a window of size 2k + 1 and updates the sum in constant time as the window moves. This avoids recomputing sums for overlapping subarrays and achieves O(n) time complexity with O(1) extra space.
Is K Radius Subarray Averages asked at Google/Amazon/Meta?
Problems involving sliding window averages and fixed-size subarray computations appear frequently in interviews at large tech companies such as Amazon, Google, and Meta. Variations of this pattern test a candidate's ability to optimize repeated calculations in arrays.
What data structure is used in K Radius Subarray Averages?
The problem primarily uses arrays along with the sliding window technique. A running integer sum is maintained while iterating through the array. No additional complex data structures are required beyond the result array.
What is the time complexity of K Radius Subarray Averages?
The optimal solution runs in O(n) time using a sliding window. Each element is added to the running sum once and removed once as the window moves across the array. A brute force implementation that recomputes each window separately takes O(n * k) time.