Maximum Average Subarray I

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^{-5} will be accepted.

Example 1:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

## Maximum Average Subarray

### Problem Description

Given an integer array `nums` consisting of `n` elements, and an integer `k`, find a contiguous subarray whose length is equal to `k` that has the maximum average value and return this value. Any answer with a calculation error less than `10^{-5}` will be accepted.

### Naive Approach

A straightforward approach would be to iterate through all possible subarrays of length `k`, calculate their averages, and find the maximum among them.

```python
def find_max_average_naive(nums, k):
    n = len(nums)
    if k > n:
        return -1  # Or raise an exception
    
    max_avg = float('-inf')
    for i in range(n - k + 1):
        current_sum = 0
        for j in range(i, i + k):
            current_sum += nums[j]
        current_avg = current_sum / k
        max_avg = max(max_avg, current_avg)
    
    return max_avg

Optimal Approach: Sliding Window

A more efficient approach is to use the sliding window technique. First, calculate the sum of the first k elements. Then, slide the window by one element at a time, subtracting the element that leaves the window and adding the element that enters the window. Keep track of the maximum sum seen so far, and finally, divide by k to get the maximum average.

def find_max_average(nums, k):
    n = len(nums)
    if k > n:
        return -1  # Or raise an exception

    current_sum = sum(nums[:k])
    max_sum = current_sum

    for i in range(k, n):
        current_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, current_sum)

    return max_sum / k

Example

nums = [1, 12, -5, -6, 50, 3]
k = 4
print(find_max_average(nums, k))  # Output: 12.75

Big O Runtime Analysis

The sliding window approach has a time complexity of O(n), where n is the length of the input array. This is because we iterate through the array only once.

Big O Space Usage Analysis

The space complexity is O(1) because we are only using a few constant space variables to store the current sum and the maximum sum.

Edge Cases and Considerations

1. Empty Array: If the input array is empty, we should return an appropriate error value or raise an exception.
2. k Greater Than Array Length: If k is greater than the length of the array, it's impossible to find a subarray of length k. We should return an error value or raise an exception.
3. Negative Numbers: The algorithm should work correctly with negative numbers in the input array.
4. Large Input: The algorithm should be efficient enough to handle large input arrays (up to 10^5 elements as stated in the constraints).

def find_max_average_with_edge_cases(nums, k):
    n = len(nums)

    if not nums:
        return 0.0  # Or raise ValueError("Input array cannot be empty")

    if k > n:
        return 0.0  # Or raise ValueError("k cannot be greater than the length of the array")

    current_sum = sum(nums[:k])
    max_sum = current_sum

    for i in range(k, n):
        current_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, current_sum)

    return max_sum / k