K-Radius Subarray Averages

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given a 0-indexed array of integers nums of length n and an integer k.

The k-radius average for a subarray of nums centered at index i is the average of all elements between indices i - k and i + k (inclusive). The average should be calculated using integer division, which truncates any fractional part.

However, if there are fewer than k elements before or after index i, the k-radius average is defined to be -1.

Your task is to build and return an array avgs of length n, where avgs[i] is the k-radius average for the subarray centered at index i.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers, N (the size of the array) and k (the radius).

The second line contains N space-separated integers, representing the elements of the nums array.

Output Format:

Print a single line containing N space-separated integers, representing the avgs array.

Note:

The window size for a valid average calculation is 2 * k + 1. The first possible center for a valid average is at index k, and the last is at index n - 1 - k. Any index outside this range will have an average of -1. A sliding window or prefix sum approach is recommended to calculate the sums efficiently.

Sample Input 1:

9 3
7 4 3 9 1 8 5 2 6

Sample Output 1:

-1 -1 -1 5 4 4 -1 -1 -1

Explanation for Sample 1:

Indices 0, 1, 2 do not have k=3 elements before them, so their averages are -1.
Index 3: Subarray is [7, 4, 3, 9, 1, 8, 5]. Sum = 37. Average = 37 / 7 = 5.
Index 4: Subarray is [4, 3, 9, 1, 8, 5, 2]. Sum = 32. Average = 32 / 7 = 4.
Index 5: Subarray is [3, 9, 1, 8, 5, 2, 6]. Sum = 34. Average = 34 / 7 = 4.

Indices 6, 7, 8 do not have k=3 elements after them, so their averages are -1.

Sample Input 2:

1 0
100000

Sample Output 2:

Explanation for Sample 2:

For k=0, the window size is 1. The average at index 0 is just the element itself, 100000 / 1 = 100000.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= n <= 10^5

0 <= nums[i], k <= 10^5

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

K-Radius Subarray Averages

Console