Scale Engineer

K Radius Subarray Averages

Med
#1902Time: O(n * k). For each of the `n` indices, we might perform a sum over `2k + 1` elements. In the worst case, this leads to O(n*k) operations.Space: O(n) to store the result array `avgs`. If the output array is not considered, the auxiliary space is O(1).1 company
Patterns
Sliding Window
Data structures
Array
Companies
Duolingo

Prompt

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, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.

 

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.length
  • 1 <= n <= 105
  • 0 <= nums[i], k <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

This is a straightforward approach where we iterate through each possible center index i. For each i, we check if it can form a valid k-radius subarray. If it can, we then iterate through all elements within the radius k of i, sum them up, and calculate the average. This process is repeated for all indices.

Algorithm

  • Create an integer array avgs of size n and fill it with -1.
  • Iterate through the input array nums with index i from 0 to n-1.
  • For each i, check if i - k >= 0 and i + k < n.
  • If the condition is true: a. Initialize a long variable sum = 0. b. Iterate with index j from i - k to i + k. c. Add nums[j] to sum. d. After the inner loop, calculate the average (int) (sum / (2 * k + 1)) and store it in avgs[i].
  • Return the avgs array.

Walkthrough

We first create an answer array avgs of the same size as nums and initialize all its values to -1. We then loop through each index i from 0 to n-1. Inside the loop, we check if the current index i can be a center of a k-radius subarray. This is possible only if there are at least k elements to its left and k elements to its right. The condition for this is i >= k and i < n - k. If the condition is not met, avgs[i] remains -1, and we move to the next index. If the condition is met, we calculate the sum of the elements in the subarray from i - k to i + k. To avoid integer overflow, we use a long variable for the sum. The number of elements in this subarray is (i + k) - (i - k) + 1 = 2k + 1. We compute the average using integer division: sum / (2k + 1). The result is stored in avgs[i]. After iterating through all indices, we return the avgs array.

import java.util.Arrays; class Solution {    public int[] getAverages(int[] nums, int k) {        int n = nums.length;        int[] avgs = new int[n];        Arrays.fill(avgs, -1);         for (int i = 0; i < n; i++) {            // Check if a valid k-radius subarray can be formed.            if (i - k >= 0 && i + k < n) {                long sum = 0;                // Calculate the sum of the subarray.                for (int j = i - k; j <= i + k; j++) {                    sum += nums[j];                }                // Calculate the average and store it.                avgs[i] = (int) (sum / (2 * k + 1));            }        }        return avgs;    }}

Complexity

Time

O(n * k). For each of the `n` indices, we might perform a sum over `2k + 1` elements. In the worst case, this leads to O(n*k) operations.

Space

O(n) to store the result array `avgs`. If the output array is not considered, the auxiliary space is O(1).

Trade-offs

Pros

  • Easy to understand and implement.

  • Directly translates the problem definition into code.

Cons

  • Highly inefficient due to repeated sum calculations for overlapping subarrays.

  • Will result in a 'Time Limit Exceeded' error for large inputs.

Solutions

class Solution {public  int[] getAverages(int[] nums, int k) {    int n = nums.length;    long[] s = new long[n + 1];    for (int i = 0; i < n; ++i) {      s[i + 1] = s[i] + nums[i];    }    int[] ans = new int[n];    Arrays.fill(ans, -1);    for (int i = 0; i < n; ++i) {      if (i - k >= 0 && i + k < n) {        ans[i] = (int)((s[i + k + 1] - s[i - k]) / (k << 1 | 1));      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem