"""
Given an array, find the average of all contiguous subarrays of size ‘K’ in it.

Comments:

The brute force algorithm is inefficient since for any two consecutive arrays,
the overlapping part containing 4 elements will be evaluated twice,
i.e `3, 2, 6, -1` in the example below for the first 2 iterations.

```
start_index: 0 sub_array: [1, 3, 2, 6, -1]
start_index: 1 sub_array: [3, 2, 6, -1, 4]
```
If we can somehow reuse the sum already calculated for the overlapping
elements then we can have better efficiency.

Visualizing each contiguous subarray as a sliding windo of size k is
helpful since we can reuse the sum from the previous subarray by
subtracting the element going out of the windo and add the element
coming into the window. This way we avoid going throught the whole
subarray to find the sum hence time complexity reduces to O(n).

"""


def find_average_for_subarrays(arr: list, k: int):
    """
    Brute force algorithm

    Time complexity: O(n*k)
    """

    sub_array_averages = []
    for i in range(len(arr) - k + 1):
        print(f"start_index: {i} sub_array: {arr[i:i+k]}")
        sub_array_sum = 0.0
        for j in range(i, i + k):
            sub_array_sum += arr[j]
        sub_array_averages.append(sub_array_sum / k)  # append average
    return sub_array_averages


def find_average_for_subarrays_sliding_window(arr: list, k: int):
    """
    Sliding window method

    Time complexity: O(n)
    """

    averages = []
    window_start = window_sum = 0
    for window_end in range(len(arr)):
        window_sum += arr[window_end]  # add next element
        if window_end >= k - 1:
            # we have finished the first window
            averages.append(window_sum / k)
            window_sum -= arr[window_start]
            # advance our window
            window_start += 1
    return averages


if __name__ == "__main__":
    arr = [1, 3, 2, 6, -1, 4, 1, 8, 2]
    k = 5
    print(f"original_array: {arr}")
    result = find_average_for_subarrays(arr, k)
    print(result)
    result = find_average_for_subarrays_sliding_window(arr, k)
    print(result)
