Maximum Average Subarray - I

Maximum Average Subarray I – LeetCode #643

Problem Statement

You are given an integer array nums containing n elements, and an integer k.
Your task is to find the contiguous subarray of length k that has the maximum average value, and return this average as a double.

Any returned result with an error less than 10⁻⁵ is considered correct.

Examples

Constraints

Intuition

This is a direct variation of the Maximum Sum Subarray of Size K problem.
The only difference is that we need to return the average instead of the sum.

We can still use the Fixed Size Sliding Window technique, where we:

  1. Compute the sum of the first k elements

  2. Slide the window one element at a time while updating the sum

  3. Keep track of the maximum sum, and finally return maxSum / k

This approach allows us to process the entire array in linear time.

Approach

  1. Initialize a variable sum to hold the sum of the first k elements.

  2. Store sum in maxSum.

  3. From index k to n-1, slide the window:

    • Add the new element at i

    • Subtract the element going out of the window at i-k

    • Update maxSum if the new sum is greater

  4. Return maxSum / k as a floating-point result

Java Code

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        
        // Step 1: Compute the initial window sum
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        int maxSum = sum;

        // Step 2: Slide the window and update maxSum
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, sum);
        }

        // Step 3: Return the average
        return (double) maxSum / k;
    }
}

Time and Space Complexity

Dry Run

Input:

nums = [1, 12, -5, -6, 50, 3], k = 4

Steps:

Output: 12.75

Conclusion

This problem is another classic application of the Fixed Size Sliding Window technique.

The key idea is that, since the window size is fixed, we can maintain the sum of the window in constant time as we slide across the array. This allows us to compute the maximum average in O(n) time, making it scalable for large arrays (up to 10⁵ elements).

This approach generalizes well for: