K Radius Subarray Averages

Problem Description

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.

Key Insights

• The k-radius average is only valid if there are at least k elements before and after the index i.
• To efficiently calculate the averages, a sliding window approach can be used to maintain the sum of the elements in the current window of size 2k + 1.
• If k is 0, the average for each index is simply the value at that index.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution employs a sliding window technique to keep track of the sum of the elements within the current window of size 2k + 1. The algorithm starts by initializing a result array filled with -1. It then iterates through the nums array while maintaining a running sum of the current window. When the window reaches the size of 2k + 1, the average is computed and stored in the results array. This approach ensures that each element is processed in constant time, leading to an overall linear time complexity.

Code Solutions