643. Maximum Average Subarray I

Description

The problem is to find the maximum average of any subarray of a given length k in an array. The subarray must be contiguous, and you need to return the maximum possible average value of such subarrays.

Intuition

The key insight is that by maintaining a sliding window sum of length k, we can efficiently calculate the sum of each subarray of length k and then compute the average. By updating this sum as we slide the window across the array, we avoid recalculating the sum from scratch, which improves the efficiency.

Approach

1. Initialize: Calculate the sum of the first k elements. This will serve as the starting point for our sliding window.
2. Sliding Window: Slide the window across the array by one element at a time, updating the sum by subtracting the element that’s left behind and adding the new element that enters the window.
3. Calculate Average: For each window position, calculate the average and update the maximum average found so far.
4. Return Result: After processing the entire array, return the maximum average found.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. This is because we only pass through the array once.

Space Complexity:

O(1), since we are using only a fixed amount of extra space for variables, regardless of the input size.

Code

C++

class Solution {
public:
    double findMaxAverage(vector& nums, int k) {
        double sum = accumulate(nums.begin(), nums.begin() + k, 0);
        double ans = -DBL_MAX;

        for (int l = 0, r = l + k - 1; l <= nums.size() - k; l++) {
            double avg = sum / k;
            ans = max(ans, avg);
            sum -= nums[l];
            r++;
            if (r < nums.size()) {
                sum += nums[r];
            }
        }

        return ans;
    }
};

Python

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        sum_val = sum(nums[:k])
        ans = -float('inf')

        for l in range(len(nums) - k + 1):
            avg = sum_val / k
            ans = max(ans, avg)
            if l + k < len(nums):
                sum_val -= nums[l]
                sum_val += nums[l + k]

        return ans

Java

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        double ans = -Double.MAX_VALUE;

        for (int l = 0, r = l + k - 1; l <= nums.length - k; l++) {
            double avg = sum / k;
            ans = Math.max(ans, avg);
            sum -= nums[l];
            r++;
            if (r < nums.length) {
                sum += nums[r];
            }
        }

        return ans;
    }
}

JavaScript

const findMaxAverage = function (x, k) {
    let sum = x.slice(0, k).reduce((acc, cur) => acc + cur, 0);
    let avg,
        ans = -Infinity;
    for (let l = 0, r = l + k - 1; l <= x.length - k; l++) {
        avg = (sum / k).toFixed(5);
        sum -= x[l];
        r++;
        sum += x[r];
        ans = Math.max(ans, avg);
    }

    return ans;
};