K Radius Subarray Averages - Leetcode Solution

Problem Statement: Given an array of integers and a positive integer k, find the average of all contiguous subarrays of size k.

Example: Input: arr=[1, 3, 2, 6, -1, 4, 1, 8, 2], k=5 Output: [2.2, 2.8, 2.4, 3.6, 2.8]

Explanation: The contiguous subarrays of size 5 are [1, 3, 2, 6, -1], [3, 2, 6, -1, 4], [2, 6, -1, 4, 1], [6, -1, 4, 1, 8], and [4, 1, 8, 2]. The averages of these subarrays are 2.2, 2.8, 2.4, 3.6, and 2.8, respectively.

Approach: The brute force approach to this problem is to calculate the average of each and every contiguous subarray of size k. This approach will take O(n*k) time complexity and will not be efficient for large arrays. An optimized approach to this problem is to use a sliding window technique. We can create a window of size k and slide it through the array. At each step, we remove the first element of the window and add the next element to it. We can calculate the sum of the elements in the window and divide it by k to get the average of that subarray. We can continue sliding the window till the end of the array is reached. This approach will take O(n) time complexity and will be efficient for large arrays.

Algorithm:

1. Initialize an empty list called "result" to store the average of all contiguous subarrays of size k.
2. Initialize two variables, "window_sum" and "window_start", to 0.
3. Slide the window through the array from left to right, one element at a time, until the end of the array is reached: a. Add the current element to the sum of the current window. b. If the current window size is greater than or equal to k: i. Calculate the average of the current window by dividing the sum of the current window by k. ii. Append the average to the "result" list. iii. Remove the first element of the current window from the sum of the current window. iv. Increment the starting index of the current window by 1.
4. Return the "result" list containing the average of all contiguous subarrays of size k.

Python Code:

def find_average_of_subarrays(arr, k): result = [] window_sum = 0.0 window_start = 0 for window_end in range(len(arr)): window_sum += arr[window_end] if window_end >= k - 1: result.append(window_sum / k) window_sum -= arr[window_start] window_start += 1 return result

Time Complexity: The time complexity of this algorithm is O(n) as we are looping through the array only once.

1